제출 #63639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63639		evpipis	낙하산 고리들 (IOI12_rings)	C++11	100 / 100	2809 ms	122148 KiB

rings

#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e6+5;
int n, state, cycle, last;
int par[5][len], deg[5][len], sz[5][len], block[5][len], fine[5];
vector<int> adj[len];
vector<ii> edge;

int fin(int t, int i){
    if (par[t][i] == i) return i;
    return par[t][i] = fin(t, par[t][i]);
}

void join(int t, int i, int j){
    i = fin(t, i), j = fin(t, j);
    if (i == j) return;

    par[t][i] = j;
    sz[t][j] += sz[t][i];
}

void build(int t, int u){
    block[t][u] = 1;

    fine[t] = 1;
    for (int i = 0; i < edge.size(); i++){
        int a = edge[i].fi, b = edge[i].se;
        if (block[t][a] || block[t][b]) continue;

        if (deg[t][a] > 1 || deg[t][b] > 1 || fin(t, a) == fin(t, b))
            fine[t] = 0;
        deg[t][a]++, deg[t][b]++;
        join(t, a, b);
    }
}

void Init(int N){
    n = N, state = 0, cycle = 0, last = 0;

    for (int t = 0; t < 5; t++)
        for (int i = 0; i < n; i++)
            par[t][i] = i, deg[t][i] = 0, sz[t][i] = 1;
}

void Link(int a, int b){
    edge.pb(mp(a, b));
    if (state == 0){
        adj[a].pb(b), adj[b].pb(a);
        deg[0][a]++, deg[0][b]++;

        if (deg[0][a] < deg[0][b])
            swap(a, b);

        if (deg[0][a] == 3){
            state = 1;
            build(1, a);
            build(2, adj[a][0]);
            build(3, adj[a][1]);
            build(4, adj[a][2]);
        }
        else{
            a = fin(0, a), b = fin(0, b);
            if (a == b)
                cycle++, last = sz[0][a];
            else
                join(0, a, b);
        }
    }
    else{
        for (int t = 1; t <= 4; t++){
            if (block[t][a] || block[t][b]) continue;

            if (deg[t][a] > 1 || deg[t][b] > 1 || fin(t, a) == fin(t, b))
                fine[t] = 0;
            deg[t][a]++, deg[t][b]++;
            join(t, a, b);
        }
    }
}

int CountCritical(){
    int ans = 0;
    if (state == 0){
        if (cycle == 0) ans = n;
        else if (cycle == 1) ans = last;
        else ans = 0;
    }
    else{
        for (int j = 1; j <= 4; j++)
            ans += fine[j];
    }

    return ans;
}

#ifdef TEST
int main() {
  freopen("example.txt", "r", stdin);
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc((1 << 16) * sizeof(char));
  outbuf = (char*) malloc((1 << 16) * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, (1 << 16));
  tmp = setvbuf(stdout, outbuf, _IOFBF, (1 << 16));

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}
#endif // TEST

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'void build(int, int)':
rings.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edge.size(); i++){
                     ~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31