답안 #69603 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69603	2018-08-21T09:48:17 Z	funcsr	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1611 ms	115812 KB

rings

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

struct UF {
  int U[1000000], R[1000000];
  void init(int N) {
    rep(i, N) U[i]=i, R[i]=1;
  }
  int find(int x) {
    if (U[x]==x)return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if(x==y)return;
    if (R[x]<R[y])swap(x,y);
    U[y]=x;
    R[x]+=R[y];
  }
  bool same(int x, int y) {
    return find(x)==find(y);
  }
};

int N;
struct Tree {
  UF uf;
  int X;
  bool dead;
  Tree() {}
  Tree(int X, vector<P> edges) : X(X), dead(false) {
    uf.init(N);
    for (P p : edges) add_edge(p._1, p._2);
  }
  void add_edge(int a, int b) {
    if (dead) return;
    if (a==X||b==X) return;
    if (uf.same(a, b)) dead = true;
    uf.unite(a, b);
  }
};


vector<int> G[1000000];
UF uf;
bool deg012 = true;
vector<int> cycles;
Tree cand[4];
vector<P> edges;

void cand_filter(vector<int> seq) {
  rep(i, 4) if (!cand[i].dead) {
    bool ok = false;
    for (int x : seq) if (x == cand[i].X) ok = true;
    if (!ok) cand[i].dead = true;
  }
}

void Init(int N_) {
  N = N_;
  uf.init(N);
}

void Link(int a, int b) {
  edges.pb(P(a, b));
  G[a].pb(b);
  G[b].pb(a);
  if (!deg012) rep(i, 4) cand[i].add_edge(a, b);

  if (G[a].size() < 3) swap(a, b);
  if (deg012 && G[a].size() >= 3) {
    deg012 = false;
    cand[0] = Tree(a, edges);
    cand[1] = Tree(G[a][0], edges);
    cand[2] = Tree(G[a][1], edges);
    cand[3] = Tree(G[a][2], edges);
  }
  if (G[a].size() == 3) cand_filter({a, G[a][0], G[a][1], G[a][2]});
  if (G[b].size() == 3) cand_filter({b, G[b][0], G[b][1], G[b][2]});
  if (G[a].size() >= 4) cand_filter({a});
  if (G[b].size() >= 4) cand_filter({b});

  if (deg012 && cycles.size() <= 1) {
    bool same = uf.same(a, b);
    uf.unite(a, b);
    if (same) cycles.pb(uf.R[uf.find(a)]);
  }
}

int CountCritical() {
  if (deg012) {
    if (cycles.size() == 0) return N;
    else if (cycles.size() == 1) return cycles[0];
    else return 0;
  }
  else {
    int s = 0;
    rep(i, 4) s += !cand[i].dead;
    return s;
  }
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	50 ms	55412 KB	Output is correct
3	Correct	50 ms	55576 KB	Output is correct
4	Correct	22 ms	55576 KB	Output is correct
5	Correct	22 ms	55576 KB	Output is correct
6	Correct	25 ms	55576 KB	Output is correct
7	Correct	48 ms	55576 KB	Output is correct
8	Correct	24 ms	55576 KB	Output is correct
9	Correct	51 ms	55712 KB	Output is correct
10	Correct	65 ms	55712 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	481 ms	55712 KB	Output is correct
2	Correct	1074 ms	99220 KB	Output is correct
3	Correct	960 ms	105736 KB	Output is correct
4	Correct	1268 ms	105736 KB	Output is correct
5	Correct	1319 ms	105736 KB	Output is correct
6	Correct	1188 ms	105736 KB	Output is correct
7	Correct	916 ms	105736 KB	Output is correct
8	Correct	1495 ms	108824 KB	Output is correct
9	Correct	1611 ms	115812 KB	Output is correct
10	Correct	859 ms	115812 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	50 ms	55412 KB	Output is correct
3	Correct	50 ms	55576 KB	Output is correct
4	Correct	22 ms	55576 KB	Output is correct
5	Correct	22 ms	55576 KB	Output is correct
6	Correct	25 ms	55576 KB	Output is correct
7	Correct	48 ms	55576 KB	Output is correct
8	Correct	24 ms	55576 KB	Output is correct
9	Correct	51 ms	55712 KB	Output is correct
10	Correct	65 ms	55712 KB	Output is correct
11	Correct	52 ms	115812 KB	Output is correct
12	Correct	56 ms	115812 KB	Output is correct
13	Correct	54 ms	115812 KB	Output is correct
14	Correct	54 ms	115812 KB	Output is correct
15	Correct	52 ms	115812 KB	Output is correct
16	Correct	26 ms	115812 KB	Output is correct
17	Correct	53 ms	115812 KB	Output is correct
18	Correct	54 ms	115812 KB	Output is correct
19	Correct	27 ms	115812 KB	Output is correct
20	Correct	54 ms	115812 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	50 ms	55412 KB	Output is correct
3	Correct	50 ms	55576 KB	Output is correct
4	Correct	22 ms	55576 KB	Output is correct
5	Correct	22 ms	55576 KB	Output is correct
6	Correct	25 ms	55576 KB	Output is correct
7	Correct	48 ms	55576 KB	Output is correct
8	Correct	24 ms	55576 KB	Output is correct
9	Correct	51 ms	55712 KB	Output is correct
10	Correct	65 ms	55712 KB	Output is correct
11	Correct	52 ms	115812 KB	Output is correct
12	Correct	56 ms	115812 KB	Output is correct
13	Correct	54 ms	115812 KB	Output is correct
14	Correct	54 ms	115812 KB	Output is correct
15	Correct	52 ms	115812 KB	Output is correct
16	Correct	26 ms	115812 KB	Output is correct
17	Correct	53 ms	115812 KB	Output is correct
18	Correct	54 ms	115812 KB	Output is correct
19	Correct	27 ms	115812 KB	Output is correct
20	Correct	54 ms	115812 KB	Output is correct
21	Correct	43 ms	115812 KB	Output is correct
22	Correct	56 ms	115812 KB	Output is correct
23	Correct	84 ms	115812 KB	Output is correct
24	Correct	96 ms	115812 KB	Output is correct
25	Correct	64 ms	115812 KB	Output is correct
26	Correct	95 ms	115812 KB	Output is correct
27	Correct	79 ms	115812 KB	Output is correct
28	Correct	100 ms	115812 KB	Output is correct
29	Correct	87 ms	115812 KB	Output is correct
30	Correct	86 ms	115812 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	50 ms	55412 KB	Output is correct
3	Correct	50 ms	55576 KB	Output is correct
4	Correct	22 ms	55576 KB	Output is correct
5	Correct	22 ms	55576 KB	Output is correct
6	Correct	25 ms	55576 KB	Output is correct
7	Correct	48 ms	55576 KB	Output is correct
8	Correct	24 ms	55576 KB	Output is correct
9	Correct	51 ms	55712 KB	Output is correct
10	Correct	65 ms	55712 KB	Output is correct
11	Correct	481 ms	55712 KB	Output is correct
12	Correct	1074 ms	99220 KB	Output is correct
13	Correct	960 ms	105736 KB	Output is correct
14	Correct	1268 ms	105736 KB	Output is correct
15	Correct	1319 ms	105736 KB	Output is correct
16	Correct	1188 ms	105736 KB	Output is correct
17	Correct	916 ms	105736 KB	Output is correct
18	Correct	1495 ms	108824 KB	Output is correct
19	Correct	1611 ms	115812 KB	Output is correct
20	Correct	859 ms	115812 KB	Output is correct
21	Correct	52 ms	115812 KB	Output is correct
22	Correct	56 ms	115812 KB	Output is correct
23	Correct	54 ms	115812 KB	Output is correct
24	Correct	54 ms	115812 KB	Output is correct
25	Correct	52 ms	115812 KB	Output is correct
26	Correct	26 ms	115812 KB	Output is correct
27	Correct	53 ms	115812 KB	Output is correct
28	Correct	54 ms	115812 KB	Output is correct
29	Correct	27 ms	115812 KB	Output is correct
30	Correct	54 ms	115812 KB	Output is correct
31	Correct	43 ms	115812 KB	Output is correct
32	Correct	56 ms	115812 KB	Output is correct
33	Correct	84 ms	115812 KB	Output is correct
34	Correct	96 ms	115812 KB	Output is correct
35	Correct	64 ms	115812 KB	Output is correct
36	Correct	95 ms	115812 KB	Output is correct
37	Correct	79 ms	115812 KB	Output is correct
38	Correct	100 ms	115812 KB	Output is correct
39	Correct	87 ms	115812 KB	Output is correct
40	Correct	86 ms	115812 KB	Output is correct
41	Correct	252 ms	115812 KB	Output is correct
42	Correct	713 ms	115812 KB	Output is correct
43	Correct	318 ms	115812 KB	Output is correct
44	Correct	725 ms	115812 KB	Output is correct
45	Correct	885 ms	115812 KB	Output is correct
46	Correct	811 ms	115812 KB	Output is correct
47	Correct	1079 ms	115812 KB	Output is correct
48	Correct	517 ms	115812 KB	Output is correct
49	Correct	802 ms	115812 KB	Output is correct
50	Correct	843 ms	115812 KB	Output is correct
51	Correct	338 ms	115812 KB	Output is correct
52	Correct	657 ms	115812 KB	Output is correct
53	Correct	516 ms	115812 KB	Output is correct
54	Correct	1360 ms	115812 KB	Output is correct
55	Correct	1191 ms	115812 KB	Output is correct

답안 #69603

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