Submission #2707880


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

const int N = 100100;
VI g[N];
bool vis[N];
int col[N];

bool is_bipartite(int v, int c) {
  if (vis[v]) {
    return c == col[v];
  }
  vis[v] = true;
  col[v] = c;
  for (int w: g[v]) {
    if (not is_bipartite(w, 1 - c)) {
      return false;
    }
  }
  return true;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  REP(i, 0, n) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int mi = n + 1;
  int mincut, maxcut = -1;
  REP(i, 0, n) {
    mi = min(mi, (int) g[i].size());
  }
  mincut = mi;
  maxcut = n - (is_bipartite(0, 0) ? 0 : 1);
  cout << mincut << " " << maxcut << endl;
}

Submission Info

Submission Time
Task C - 最小カットと最大カット
User kobae964
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1274 Byte
Status AC
Exec Time 40 ms
Memory 9344 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 29
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 AC 2 ms 2560 KB
scrambled_02.txt AC 2 ms 2560 KB
scrambled_03.txt AC 40 ms 9344 KB
scrambled_04.txt AC 40 ms 9344 KB
scrambled_05.txt AC 24 ms 6784 KB
scrambled_06.txt AC 16 ms 5248 KB
scrambled_07.txt AC 37 ms 8832 KB
scrambled_08.txt AC 13 ms 4736 KB
scrambled_09.txt AC 17 ms 5376 KB
scrambled_10.txt AC 26 ms 6648 KB
scrambled_11.txt AC 11 ms 4092 KB
scrambled_12.txt AC 21 ms 5880 KB
scrambled_13.txt AC 20 ms 5624 KB
scrambled_14.txt AC 37 ms 6272 KB
scrambled_15.txt AC 26 ms 5120 KB
scrambled_16.txt AC 14 ms 3968 KB
scrambled_17.txt AC 14 ms 3968 KB
scrambled_18.txt AC 38 ms 6272 KB
scrambled_19.txt AC 4 ms 2944 KB
scrambled_20.txt AC 23 ms 4992 KB
scrambled_21.txt AC 13 ms 3968 KB
scrambled_22.txt AC 24 ms 5248 KB
scrambled_23.txt AC 21 ms 4224 KB
scrambled_24.txt AC 15 ms 4096 KB
scrambled_25.txt AC 18 ms 4480 KB
scrambled_26.txt AC 15 ms 4096 KB
scrambled_27.txt AC 23 ms 4864 KB
scrambled_28.txt AC 20 ms 4736 KB