답안 #216716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216716	2020-03-27T21:29:28 Z	DS007	게임 (IOI14_game)	C++14	15 / 100	5 ms	384 KB

game

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

class DSU {
    int *par, *val;
    int n, count;

public:
    DSU(int n) {
        this->n = n;
        count = 0;
        par = new int[n];
        val = new int[n];
        iota(par, par + n, 0);
        fill(val, val + n, n - 1);
    }

    int find(int v) {
        if (v == par[v])
            return v;
        else
            return par[v] = find(par[v]);
    }

    int merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb)
            return 0;

        par[pa] = pb;
        val[pb] += val[pa] - 2;
        return 1;
    }

    int get(int v) {
        return val[find(v)];
    }

    int update(int u, int v) {
        val[find(u)]--;
        val[find(v)]--;
        count++;
        return 0;
    }

    bool check() {
        return count < (n - 1) * (n - 2) / 2;
    }
};

DSU *dsu;

void initialize(int n) {
    dsu = new DSU(n);
}

int hasEdge(int u, int v) {
    int pu = dsu->find(u), pv = dsu->find(v);
    if (pu == pv)
        return 1;
    if (dsu->get(pu) != 1 && dsu->get(pv) != 1 && dsu->check())
        return dsu->update(pu, pv);
    else
        return dsu->merge(pu, pv);
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	256 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	256 KB	Output is correct
4	Correct	4 ms	256 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	4 ms	256 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	4 ms	256 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	4 ms	256 KB	Output is correct
12	Correct	4 ms	256 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	5 ms	256 KB	Output is correct
15	Correct	4 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	4 ms	256 KB	Output is correct
18	Correct	4 ms	256 KB	Output is correct
19	Correct	5 ms	256 KB	Output is correct
20	Correct	4 ms	384 KB	Output is correct
21	Correct	4 ms	256 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct
23	Correct	5 ms	256 KB	Output is correct
24	Correct	4 ms	256 KB	Output is correct

Subtask #2

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	256 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	4 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 ms	256 KB	Output is correct
8	Correct	4 ms	256 KB	Output is correct
9	Correct	4 ms	256 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	4 ms	256 KB	Output is correct
12	Correct	4 ms	384 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	4 ms	256 KB	Output is correct
15	Correct	4 ms	256 KB	Output is correct
16	Correct	5 ms	256 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	5 ms	256 KB	Output is correct
19	Correct	5 ms	256 KB	Output is correct
20	Correct	4 ms	256 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	4 ms	256 KB	Output is correct
23	Correct	4 ms	256 KB	Output is correct
24	Correct	5 ms	256 KB	Output is correct
25	Incorrect	5 ms	256 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3

0 / 58.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	4 ms	256 KB	Output is correct
4	Correct	5 ms	256 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	256 KB	Output is correct
7	Correct	4 ms	256 KB	Output is correct
8	Correct	4 ms	256 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	5 ms	256 KB	Output is correct
12	Correct	4 ms	256 KB	Output is correct
13	Correct	4 ms	256 KB	Output is correct
14	Correct	5 ms	256 KB	Output is correct
15	Correct	4 ms	256 KB	Output is correct
16	Correct	4 ms	256 KB	Output is correct
17	Correct	4 ms	256 KB	Output is correct
18	Correct	4 ms	256 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	4 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	4 ms	256 KB	Output is correct
23	Correct	4 ms	384 KB	Output is correct
24	Correct	4 ms	256 KB	Output is correct
25	Incorrect	5 ms	256 KB	Output isn't correct
26	Halted	0 ms	0 KB	-