oj.uz

Submission #800081

# Submission time Handle Problem Language Result Execution time Memory
800081 2023-08-01T09:53:44 Z PixelCat Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 174 ms 23048 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) if(v1 != v2) {
            mask |= (1 << p[v1][v2]);
        }
        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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 174 ms 22032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 174 ms 22032 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1192 KB Output is correct
13 Correct 148 ms 22008 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory 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 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 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 37 ms 6260 KB Output is correct
5 Correct 152 ms 22912 KB Output is correct
6 Correct 149 ms 22872 KB Output is correct
7 Correct 160 ms 23048 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 40 ms 6168 KB Output is correct
10 Correct 150 ms 22920 KB Output is correct
11 Correct 156 ms 22964 KB Output is correct
12 Correct 155 ms 22660 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 0 ms 212 KB Too few ways to get from 0 to 1, should be 2 found 0
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 174 ms 22032 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1192 KB Output is correct
13 Correct 148 ms 22008 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 174 ms 22032 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1192 KB Output is correct
13 Correct 148 ms 22008 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -