답안 #800075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800075	2023-08-01T09:48:25 Z	PixelCat	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	173 ms	22092 KB

supertrees

#include "supertrees.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;

vector<vector<int>> answer;
inline void add_edge(int a, int b) {
    answer[a][b] = answer[b][a] = 1;
}

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    bool lead(int n) {
        return p[n] < 0;
    }
} dsu;

int construct(vector<vector<int>> p) {
    int n = sz(p);
    For(i, 0, n - 1) For(j, 0, n - 1) if(p[i][j] == 3) return 0;
    answer = vector<vector<int>>(n, vector<int>(n, 0));

    // phase 1: find all CC
    dsu.init();
    For(i, 0, n - 1) For(j, 0, n - 1) {
        if(p[i][j]) dsu.uni(i, j);
    }
    vector<vector<int>> vcc;
    For(i, 0, n - 1) if(dsu.lead(i)) {
        vcc.eb();
        For(j, 0, n - 1) if(dsu.same(i, j)) {
            vcc.back().eb(j);
        }
    }

    // phase 2: solve for each CC
    for(vector<int> &cc:vcc) {
        for(auto &v1:cc) for(auto &v2:cc) {
            if(p[v1][v2] != 1) return 0;
        }
        int rt = cc.back();
        cc.pop_back();
        for(auto &i:cc) {
            add_edge(i, rt);
        }
    }

    build(answer);
    return 1;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1108 KB	Output is correct
7	Correct	164 ms	22024 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1108 KB	Output is correct
7	Correct	164 ms	22024 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1108 KB	Output is correct
13	Correct	173 ms	22036 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	74 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	43 ms	5728 KB	Output is correct
21	Correct	160 ms	22020 KB	Output is correct
22	Correct	156 ms	22008 KB	Output is correct
23	Correct	158 ms	22016 KB	Output is correct
24	Correct	154 ms	22016 KB	Output is correct
25	Correct	64 ms	12052 KB	Output is correct
26	Correct	65 ms	12164 KB	Output is correct
27	Correct	163 ms	22032 KB	Output is correct
28	Correct	149 ms	22092 KB	Output is correct

Subtask #3
0 / 19.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Incorrect	212 KB	Answer gives possible 0 while actual possible 1
6	Halted	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	340 KB	Answer gives possible 0 while actual possible 1
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1108 KB	Output is correct
7	Correct	164 ms	22024 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1108 KB	Output is correct
13	Correct	173 ms	22036 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	74 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	43 ms	5728 KB	Output is correct
21	Correct	160 ms	22020 KB	Output is correct
22	Correct	156 ms	22008 KB	Output is correct
23	Correct	158 ms	22016 KB	Output is correct
24	Correct	154 ms	22016 KB	Output is correct
25	Correct	64 ms	12052 KB	Output is correct
26	Correct	65 ms	12164 KB	Output is correct
27	Correct	163 ms	22032 KB	Output is correct
28	Correct	149 ms	22092 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Incorrect	0 ms	212 KB	Answer gives possible 0 while actual possible 1
34	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1108 KB	Output is correct
7	Correct	164 ms	22024 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	7 ms	1108 KB	Output is correct
13	Correct	173 ms	22036 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	74 ms	12040 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	43 ms	5728 KB	Output is correct
21	Correct	160 ms	22020 KB	Output is correct
22	Correct	156 ms	22008 KB	Output is correct
23	Correct	158 ms	22016 KB	Output is correct
24	Correct	154 ms	22016 KB	Output is correct
25	Correct	64 ms	12052 KB	Output is correct
26	Correct	65 ms	12164 KB	Output is correct
27	Correct	163 ms	22032 KB	Output is correct
28	Correct	149 ms	22092 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Incorrect	0 ms	212 KB	Answer gives possible 0 while actual possible 1
34	Halted	0 ms	0 KB	-

답안 #800075

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0