Submission #1344422


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define long long long // for codeforces

vector<int> vec[100005];
int num[100005];
int c;

void dfs(int d, int from, int dep){
  num[d]=dep;
  for(auto to : vec[d]) if(to!=from){
    if(num[d]!=-1){
      c = dep-num[d]+1;
    }
    else dfs(to, d, dep+1);
  }
}

int main(){
  int n;
  cin>>n;
  rep(i,n){
    int a,b;
    cin>>a>>b;
    a--;b--;
    vec[a].pb(b);
    vec[b].pb(a);
  }
  fill(num, num+n, -1);
  dfs(0,-1,0);

  int mn,mx;
  if(c==n) mn=2;
  else mn=1;

  if(c%2==0) mx=n;
  else mx=n-1;

  cout << mn << " " << mx << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 最小カットと最大カット
User tossy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1242 Byte
Status WA
Exec Time 88 ms
Memory 6520 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 13
WA × 16
Set Name Test Cases
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 2 ms 2560 KB
scrambled_01.txt WA 2 ms 2560 KB
scrambled_02.txt WA 2 ms 2560 KB
scrambled_03.txt WA 86 ms 6144 KB
scrambled_04.txt WA 85 ms 6144 KB
scrambled_05.txt WA 53 ms 4736 KB
scrambled_06.txt WA 33 ms 3968 KB
scrambled_07.txt WA 79 ms 5888 KB
scrambled_08.txt WA 27 ms 3712 KB
scrambled_09.txt WA 36 ms 3968 KB
scrambled_10.txt AC 80 ms 6520 KB
scrambled_11.txt AC 31 ms 4092 KB
scrambled_12.txt AC 64 ms 5752 KB
scrambled_13.txt AC 59 ms 5496 KB
scrambled_14.txt AC 88 ms 6144 KB
scrambled_15.txt AC 61 ms 5120 KB
scrambled_16.txt WA 32 ms 3840 KB
scrambled_17.txt WA 32 ms 3968 KB
scrambled_18.txt WA 86 ms 6272 KB
scrambled_19.txt AC 8 ms 2944 KB
scrambled_20.txt AC 54 ms 4864 KB
scrambled_21.txt AC 32 ms 3968 KB
scrambled_22.txt AC 60 ms 5120 KB
scrambled_23.txt WA 36 ms 4096 KB
scrambled_24.txt WA 33 ms 3968 KB
scrambled_25.txt AC 43 ms 4352 KB
scrambled_26.txt WA 35 ms 4096 KB
scrambled_27.txt WA 52 ms 4864 KB
scrambled_28.txt AC 48 ms 4608 KB