oj.uz

Submission #800079

# Submission time Handle Problem Language Result Execution time Memory
800079 2023-08-01T09:50:39 Z PixelCat Connecting Supertrees (IOI20_supertrees) C++14
21 / 100
 161 ms 24144 KB 
#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) {
        int mask = 0;
        for(auto &v1:cc) for(auto &v2:cc) {
            mask |= (1 << p[v1][v2]);
        }
        if(mask & 1) return 0;
        if(mask == 2) {
            int rt = cc.back();
            cc.pop_back();
            for(auto &i:cc) {
                add_edge(i, rt);
            }
        } else if(mask == 4) {
            For(i, 1, sz(cc) - 1) {
                add_edge(cc[i], cc[i - 1]);
            }
            add_edge(cc.front(), cc.back());
        }
    }

    build(answer);
    return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 161 ms 23932 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 161 ms 23932 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1212 KB Output is correct
13 Correct 150 ms 24012 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 71 ms 14028 KB Output is correct
18 Correct 0 ms 308 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 40 ms 6260 KB Output is correct
21 Correct 152 ms 24012 KB Output is correct
22 Correct 154 ms 23972 KB Output is correct
23 Correct 156 ms 23940 KB Output is correct
24 Correct 154 ms 23988 KB Output is correct
25 Correct 62 ms 14028 KB Output is correct
26 Correct 61 ms 14076 KB Output is correct
27 Correct 156 ms 23940 KB Output is correct
28 Correct 153 ms 24144 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Too few ways to get from 0 to 1, should be 2 found 0
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 161 ms 23932 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1212 KB Output is correct
13 Correct 150 ms 24012 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 71 ms 14028 KB Output is correct
18 Correct 0 ms 308 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 40 ms 6260 KB Output is correct
21 Correct 152 ms 24012 KB Output is correct
22 Correct 154 ms 23972 KB Output is correct
23 Correct 156 ms 23940 KB Output is correct
24 Correct 154 ms 23988 KB Output is correct
25 Correct 62 ms 14028 KB Output is correct
26 Correct 61 ms 14076 KB Output is correct
27 Correct 156 ms 23940 KB Output is correct
28 Correct 153 ms 24144 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 161 ms 23932 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1212 KB Output is correct
13 Correct 150 ms 24012 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 71 ms 14028 KB Output is correct
18 Correct 0 ms 308 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 40 ms 6260 KB Output is correct
21 Correct 152 ms 24012 KB Output is correct
22 Correct 154 ms 23972 KB Output is correct
23 Correct 156 ms 23940 KB Output is correct
24 Correct 154 ms 23988 KB Output is correct
25 Correct 62 ms 14028 KB Output is correct
26 Correct 61 ms 14076 KB Output is correct
27 Correct 156 ms 23940 KB Output is correct
28 Correct 153 ms 24144 KB Output is correct
29 Correct 1 ms 308 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -