답안 #69621 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69621	2018-08-21T10:14:55 Z	funcsr	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1679 ms	110060 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 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;
bool all_dead = false;

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) {
  if (all_dead) return;
  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});
  int s = 0;
  rep(i, 4) s += !cand[i].dead;
  if (s == 0) all_dead = true;

  if (deg012) {
    bool same = uf.same(a, b);
    uf.unite(a, b);
    if (same) cycles.pb(uf.R[uf.find(a)]);
    if (cycles.size() >= 2) all_dead = true;
  }
}

int CountCritical() {
  if (all_dead) return 0;
  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	55540 KB	Output is correct
3	Correct	50 ms	55640 KB	Output is correct
4	Correct	22 ms	55640 KB	Output is correct
5	Correct	23 ms	55640 KB	Output is correct
6	Correct	27 ms	55640 KB	Output is correct
7	Correct	49 ms	55640 KB	Output is correct
8	Correct	24 ms	55640 KB	Output is correct
9	Correct	56 ms	55776 KB	Output is correct
10	Correct	56 ms	55776 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	483 ms	55776 KB	Output is correct
2	Correct	1097 ms	99388 KB	Output is correct
3	Correct	342 ms	99388 KB	Output is correct
4	Correct	1295 ms	99388 KB	Output is correct
5	Correct	1234 ms	99388 KB	Output is correct
6	Correct	1209 ms	99388 KB	Output is correct
7	Correct	347 ms	99388 KB	Output is correct
8	Correct	1560 ms	106880 KB	Output is correct
9	Correct	1679 ms	110060 KB	Output is correct
10	Correct	857 ms	110060 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	55540 KB	Output is correct
3	Correct	50 ms	55640 KB	Output is correct
4	Correct	22 ms	55640 KB	Output is correct
5	Correct	23 ms	55640 KB	Output is correct
6	Correct	27 ms	55640 KB	Output is correct
7	Correct	49 ms	55640 KB	Output is correct
8	Correct	24 ms	55640 KB	Output is correct
9	Correct	56 ms	55776 KB	Output is correct
10	Correct	56 ms	55776 KB	Output is correct
11	Correct	52 ms	110060 KB	Output is correct
12	Correct	71 ms	110060 KB	Output is correct
13	Correct	53 ms	110060 KB	Output is correct
14	Correct	51 ms	110060 KB	Output is correct
15	Correct	55 ms	110060 KB	Output is correct
16	Correct	30 ms	110060 KB	Output is correct
17	Correct	51 ms	110060 KB	Output is correct
18	Correct	51 ms	110060 KB	Output is correct
19	Correct	27 ms	110060 KB	Output is correct
20	Correct	58 ms	110060 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	55540 KB	Output is correct
3	Correct	50 ms	55640 KB	Output is correct
4	Correct	22 ms	55640 KB	Output is correct
5	Correct	23 ms	55640 KB	Output is correct
6	Correct	27 ms	55640 KB	Output is correct
7	Correct	49 ms	55640 KB	Output is correct
8	Correct	24 ms	55640 KB	Output is correct
9	Correct	56 ms	55776 KB	Output is correct
10	Correct	56 ms	55776 KB	Output is correct
11	Correct	52 ms	110060 KB	Output is correct
12	Correct	71 ms	110060 KB	Output is correct
13	Correct	53 ms	110060 KB	Output is correct
14	Correct	51 ms	110060 KB	Output is correct
15	Correct	55 ms	110060 KB	Output is correct
16	Correct	30 ms	110060 KB	Output is correct
17	Correct	51 ms	110060 KB	Output is correct
18	Correct	51 ms	110060 KB	Output is correct
19	Correct	27 ms	110060 KB	Output is correct
20	Correct	58 ms	110060 KB	Output is correct
21	Correct	44 ms	110060 KB	Output is correct
22	Correct	63 ms	110060 KB	Output is correct
23	Correct	73 ms	110060 KB	Output is correct
24	Correct	98 ms	110060 KB	Output is correct
25	Correct	64 ms	110060 KB	Output is correct
26	Correct	107 ms	110060 KB	Output is correct
27	Correct	76 ms	110060 KB	Output is correct
28	Correct	75 ms	110060 KB	Output is correct
29	Correct	74 ms	110060 KB	Output is correct
30	Correct	89 ms	110060 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	55540 KB	Output is correct
3	Correct	50 ms	55640 KB	Output is correct
4	Correct	22 ms	55640 KB	Output is correct
5	Correct	23 ms	55640 KB	Output is correct
6	Correct	27 ms	55640 KB	Output is correct
7	Correct	49 ms	55640 KB	Output is correct
8	Correct	24 ms	55640 KB	Output is correct
9	Correct	56 ms	55776 KB	Output is correct
10	Correct	56 ms	55776 KB	Output is correct
11	Correct	483 ms	55776 KB	Output is correct
12	Correct	1097 ms	99388 KB	Output is correct
13	Correct	342 ms	99388 KB	Output is correct
14	Correct	1295 ms	99388 KB	Output is correct
15	Correct	1234 ms	99388 KB	Output is correct
16	Correct	1209 ms	99388 KB	Output is correct
17	Correct	347 ms	99388 KB	Output is correct
18	Correct	1560 ms	106880 KB	Output is correct
19	Correct	1679 ms	110060 KB	Output is correct
20	Correct	857 ms	110060 KB	Output is correct
21	Correct	52 ms	110060 KB	Output is correct
22	Correct	71 ms	110060 KB	Output is correct
23	Correct	53 ms	110060 KB	Output is correct
24	Correct	51 ms	110060 KB	Output is correct
25	Correct	55 ms	110060 KB	Output is correct
26	Correct	30 ms	110060 KB	Output is correct
27	Correct	51 ms	110060 KB	Output is correct
28	Correct	51 ms	110060 KB	Output is correct
29	Correct	27 ms	110060 KB	Output is correct
30	Correct	58 ms	110060 KB	Output is correct
31	Correct	44 ms	110060 KB	Output is correct
32	Correct	63 ms	110060 KB	Output is correct
33	Correct	73 ms	110060 KB	Output is correct
34	Correct	98 ms	110060 KB	Output is correct
35	Correct	64 ms	110060 KB	Output is correct
36	Correct	107 ms	110060 KB	Output is correct
37	Correct	76 ms	110060 KB	Output is correct
38	Correct	75 ms	110060 KB	Output is correct
39	Correct	74 ms	110060 KB	Output is correct
40	Correct	89 ms	110060 KB	Output is correct
41	Correct	274 ms	110060 KB	Output is correct
42	Correct	713 ms	110060 KB	Output is correct
43	Correct	311 ms	110060 KB	Output is correct
44	Correct	354 ms	110060 KB	Output is correct
45	Correct	563 ms	110060 KB	Output is correct
46	Correct	782 ms	110060 KB	Output is correct
47	Correct	1094 ms	110060 KB	Output is correct
48	Correct	320 ms	110060 KB	Output is correct
49	Correct	800 ms	110060 KB	Output is correct
50	Correct	842 ms	110060 KB	Output is correct
51	Correct	332 ms	110060 KB	Output is correct
52	Correct	327 ms	110060 KB	Output is correct
53	Correct	283 ms	110060 KB	Output is correct
54	Correct	1326 ms	110060 KB	Output is correct
55	Correct	1233 ms	110060 KB	Output is correct

답안 #69621

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