답안 #600220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600220	2022-07-20T14:30:03 Z	MilosMilutinovic	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	1846 ms	111388 KB

rings

/**
 *    author:  wxhtzdy
 *    created: 18.07.2022 00:00:16
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

const int MAXN = 1000005;

vector<int> g[MAXN];
int vis[MAXN];
int prv[MAXN];
int deg[4][MAXN];
int good[MAXN];
int ver[4];

vector<int> cyc;
vector<pair<int, int>> edges;

vector<dsu> f(4, dsu(MAXN));

int state, ans;
dsu d(MAXN);

void state1(int v) {
  state = 1;
  ans = 0;
  for (int i = 0; i < MAXN; i++) {
    if (d.get(i) == d.get(v)) {
      ans += 1;
    }
  }
}

void state2(int i) {
  ver[0] = i;
  assert((int) g[i].size() == 3);
  for (int j = 0; j < (int) g[i].size(); j++) {
    ver[1 + j] = g[i][j];
  }
  for (int i = 0; i < 4; i++) {
    good[i] = true;
  } 
  for (auto& p : edges) {
    int u = p.first;
    int v = p.second;
    for (int i = 0; i < 4; i++) {
      if (ver[i] == u || ver[i] == v) {
        continue;
      }
      ++deg[i][u];
      ++deg[i][v];
      if (deg[i][u] >= 3) {
        good[i] = false;
      }      
      if (deg[i][v] >= 3) {
        good[i] = false;
      }
      if (!f[i].unite(u, v)) {
        good[i] = false;
      }
    }
  }
  state = 2;                     
}

void state3() {
  state = 3;
  ans = 0;
}

void Init(int n) {
  state = 0;
  ans = n;
}

void Link(int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
  edges.emplace_back(a, b);
  if (state == 0 || state == 1) {
    if (d.unite(a, b)) {
      if ((int) g[a].size() >= 3) {
        state2(a);
      } else if ((int) g[b].size() >= 3) {
        state2(b);
      }
    } else {
      if (state == 0) {
        state1(a);   
      } else {
        state3();
      }
    }
  } else if (state == 2) {
    for (int i = 0; i < 4; i++) {
      if (ver[i] == a || ver[i] == b) {
        continue;
      }
      ++deg[i][a];
      ++deg[i][b];
      if (deg[i][a] >= 3) {
        good[i] = false;
      }      
      if (deg[i][b] >= 3) {
        good[i] = false;
      }
      if (!f[i].unite(a, b)) {
        good[i] = false;
      }
    }   
  }
} 

int CountCritical() {
  if (state == 2) {
    ans = 0;
    for (int i = 0; i < 4; i++) {
      if (good[i]) {
        ans += 1;
      }
    }
  }
  return ans;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	43348 KB	Output is correct
2	Correct	24 ms	43612 KB	Output is correct
3	Correct	26 ms	43788 KB	Output is correct
4	Correct	27 ms	43352 KB	Output is correct
5	Correct	28 ms	43512 KB	Output is correct
6	Correct	34 ms	43688 KB	Output is correct
7	Correct	24 ms	43536 KB	Output is correct
8	Correct	29 ms	43476 KB	Output is correct
9	Correct	24 ms	43680 KB	Output is correct
10	Correct	24 ms	43732 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	332 ms	63696 KB	Output is correct
2	Correct	1129 ms	87280 KB	Output is correct
3	Correct	1846 ms	106480 KB	Output is correct
4	Correct	897 ms	95840 KB	Output is correct
5	Correct	938 ms	95868 KB	Output is correct
6	Correct	872 ms	94256 KB	Output is correct
7	Correct	1762 ms	104996 KB	Output is correct
8	Correct	1389 ms	107280 KB	Output is correct
9	Correct	1563 ms	111388 KB	Output is correct
10	Correct	649 ms	93300 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	43348 KB	Output is correct
2	Correct	24 ms	43612 KB	Output is correct
3	Correct	26 ms	43788 KB	Output is correct
4	Correct	27 ms	43352 KB	Output is correct
5	Correct	28 ms	43512 KB	Output is correct
6	Correct	34 ms	43688 KB	Output is correct
7	Correct	24 ms	43536 KB	Output is correct
8	Correct	29 ms	43476 KB	Output is correct
9	Correct	24 ms	43680 KB	Output is correct
10	Correct	24 ms	43732 KB	Output is correct
11	Correct	30 ms	43656 KB	Output is correct
12	Correct	31 ms	44052 KB	Output is correct
13	Correct	26 ms	44108 KB	Output is correct
14	Correct	26 ms	43812 KB	Output is correct
15	Correct	27 ms	44040 KB	Output is correct
16	Correct	29 ms	43920 KB	Output is correct
17	Correct	38 ms	44032 KB	Output is correct
18	Correct	28 ms	44304 KB	Output is correct
19	Correct	28 ms	43920 KB	Output is correct
20	Correct	28 ms	44176 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	43348 KB	Output is correct
2	Correct	24 ms	43612 KB	Output is correct
3	Correct	26 ms	43788 KB	Output is correct
4	Correct	27 ms	43352 KB	Output is correct
5	Correct	28 ms	43512 KB	Output is correct
6	Correct	34 ms	43688 KB	Output is correct
7	Correct	24 ms	43536 KB	Output is correct
8	Correct	29 ms	43476 KB	Output is correct
9	Correct	24 ms	43680 KB	Output is correct
10	Correct	24 ms	43732 KB	Output is correct
11	Correct	30 ms	43656 KB	Output is correct
12	Correct	31 ms	44052 KB	Output is correct
13	Correct	26 ms	44108 KB	Output is correct
14	Correct	26 ms	43812 KB	Output is correct
15	Correct	27 ms	44040 KB	Output is correct
16	Correct	29 ms	43920 KB	Output is correct
17	Correct	38 ms	44032 KB	Output is correct
18	Correct	28 ms	44304 KB	Output is correct
19	Correct	28 ms	43920 KB	Output is correct
20	Correct	28 ms	44176 KB	Output is correct
21	Correct	37 ms	44936 KB	Output is correct
22	Correct	45 ms	45812 KB	Output is correct
23	Correct	60 ms	46604 KB	Output is correct
24	Correct	71 ms	47668 KB	Output is correct
25	Correct	36 ms	45484 KB	Output is correct
26	Correct	65 ms	48332 KB	Output is correct
27	Correct	66 ms	47760 KB	Output is correct
28	Correct	86 ms	49236 KB	Output is correct
29	Correct	80 ms	47396 KB	Output is correct
30	Correct	99 ms	48488 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	43348 KB	Output is correct
2	Correct	24 ms	43612 KB	Output is correct
3	Correct	26 ms	43788 KB	Output is correct
4	Correct	27 ms	43352 KB	Output is correct
5	Correct	28 ms	43512 KB	Output is correct
6	Correct	34 ms	43688 KB	Output is correct
7	Correct	24 ms	43536 KB	Output is correct
8	Correct	29 ms	43476 KB	Output is correct
9	Correct	24 ms	43680 KB	Output is correct
10	Correct	24 ms	43732 KB	Output is correct
11	Correct	332 ms	63696 KB	Output is correct
12	Correct	1129 ms	87280 KB	Output is correct
13	Correct	1846 ms	106480 KB	Output is correct
14	Correct	897 ms	95840 KB	Output is correct
15	Correct	938 ms	95868 KB	Output is correct
16	Correct	872 ms	94256 KB	Output is correct
17	Correct	1762 ms	104996 KB	Output is correct
18	Correct	1389 ms	107280 KB	Output is correct
19	Correct	1563 ms	111388 KB	Output is correct
20	Correct	649 ms	93300 KB	Output is correct
21	Correct	30 ms	43656 KB	Output is correct
22	Correct	31 ms	44052 KB	Output is correct
23	Correct	26 ms	44108 KB	Output is correct
24	Correct	26 ms	43812 KB	Output is correct
25	Correct	27 ms	44040 KB	Output is correct
26	Correct	29 ms	43920 KB	Output is correct
27	Correct	38 ms	44032 KB	Output is correct
28	Correct	28 ms	44304 KB	Output is correct
29	Correct	28 ms	43920 KB	Output is correct
30	Correct	28 ms	44176 KB	Output is correct
31	Correct	37 ms	44936 KB	Output is correct
32	Correct	45 ms	45812 KB	Output is correct
33	Correct	60 ms	46604 KB	Output is correct
34	Correct	71 ms	47668 KB	Output is correct
35	Correct	36 ms	45484 KB	Output is correct
36	Correct	65 ms	48332 KB	Output is correct
37	Correct	66 ms	47760 KB	Output is correct
38	Correct	86 ms	49236 KB	Output is correct
39	Correct	80 ms	47396 KB	Output is correct
40	Correct	99 ms	48488 KB	Output is correct
41	Correct	213 ms	56968 KB	Output is correct
42	Correct	688 ms	82716 KB	Output is correct
43	Correct	380 ms	65440 KB	Output is correct
44	Correct	941 ms	104936 KB	Output is correct
45	Correct	1244 ms	94660 KB	Output is correct
46	Correct	577 ms	87972 KB	Output is correct
47	Correct	815 ms	88612 KB	Output is correct
48	Correct	624 ms	84444 KB	Output is correct
49	Correct	548 ms	84836 KB	Output is correct
50	Correct	605 ms	84508 KB	Output is correct
51	Correct	308 ms	65748 KB	Output is correct
52	Correct	799 ms	93724 KB	Output is correct
53	Correct	629 ms	84988 KB	Output is correct
54	Correct	1195 ms	99324 KB	Output is correct
55	Correct	1336 ms	104064 KB	Output is correct

답안 #600220

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0