oj.uz

Submission #521330

# Submission time Handle Problem Language Result Execution time Memory
521330 2022-02-01T18:03:21 Z ddy888 Connecting Supertrees (IOI20_supertrees) C++17
21 / 100
 199 ms 28040 KB 
#include "supertrees.h"
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#include <vector>

int N;
vector<vector<int> > A;
vector<vector<int> > twos;
vector<vector<int> > ans;

struct DSU {
    vector<int> par;
    void init(int x) { par.resize(x + 1); for (int i = 0; i <= N; ++i) par[i] = i; }
    int root(int x) { return (par[x]==x)? x:par[x]=root(par[x]); }
    bool same(int a, int b) { return root(a) == root(b); }
    void merge(int a, int b) {par[root(a)] = root(b);}
};

void link(int x, int y) {
    if (x == y) return;
    ans[x - 1][y - 1] = ans[y - 1][x - 1] = 1;
}

int construct(std::vector<std::vector<int>> p) {
    N = p.size();
    A.resize(N + 1, vector<int>(N + 1));
    ans.resize(N, vector<int>(N));
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) A[i][j] = p[i - 1][j - 1];
    
    DSU dsu1, dsu2;
    dsu1.init(N);
    dsu2.init(N);
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (A[i][j] == 3) return 0;
            if (A[i][j] == 1) {
                if (dsu1.same(i, j)) continue;
                dsu1.merge(i, j);
                link(i, dsu1.root(i)); link(j, dsu1.root(j));
            } 
        }
    }
    for (int i = 1; i <= N; ++i) {
        bool non = false;
        for (int j = i + 1; j <= N; ++j) {
            if (A[i][j] == 1) non = true;
        }
        if (!non) {
            vector<int> nodes;
            nodes.pb(i);
            for (int j = i + 1; j <= N; ++j) {
                if (A[i][j] == 2) {
                    nodes.pb(j);
                }   
            }
            twos.pb(nodes);
        }
    }
    for (auto st: twos) {
        int ss = st.size();
        for (int i = 1; i < ss; ++i) {
            dsu1.merge(st[i], st[i - 1]);
            link(st[i], st[i - 1]);
        }
        link(st[0], st[ss - 1]);
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (A[i][j] == 0 && dsu1.same(i, j)) return 0;
        }
    }
    build(ans);
    return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 1412 KB Output is correct
7 Correct 180 ms 27872 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 1412 KB Output is correct
7 Correct 180 ms 27872 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 284 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 1320 KB Output is correct
13 Correct 191 ms 28016 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 4 ms 944 KB Output is correct
17 Correct 85 ms 17988 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 7148 KB Output is correct
21 Correct 179 ms 27900 KB Output is correct
22 Correct 184 ms 27888 KB Output is correct
23 Correct 185 ms 27984 KB Output is correct
24 Correct 177 ms 27932 KB Output is correct
25 Correct 82 ms 18028 KB Output is correct
26 Correct 78 ms 18004 KB Output is correct
27 Correct 187 ms 27884 KB Output is correct
28 Correct 185 ms 27940 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 49 ms 7136 KB Output is correct
5 Correct 182 ms 27928 KB Output is correct
6 Correct 199 ms 28040 KB Output is correct
7 Correct 190 ms 27940 KB Output is correct
8 Incorrect 1 ms 204 KB Too many ways to get from 0 to 3, should be 2 found no less than 3
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 1412 KB Output is correct
7 Correct 180 ms 27872 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 284 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 1320 KB Output is correct
13 Correct 191 ms 28016 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 4 ms 944 KB Output is correct
17 Correct 85 ms 17988 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 7148 KB Output is correct
21 Correct 179 ms 27900 KB Output is correct
22 Correct 184 ms 27888 KB Output is correct
23 Correct 185 ms 27984 KB Output is correct
24 Correct 177 ms 27932 KB Output is correct
25 Correct 82 ms 18028 KB Output is correct
26 Correct 78 ms 18004 KB Output is correct
27 Correct 187 ms 27884 KB Output is correct
28 Correct 185 ms 27940 KB Output is correct
29 Correct 1 ms 292 KB Output is correct
30 Correct 1 ms 292 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 1412 KB Output is correct
7 Correct 180 ms 27872 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 284 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 1320 KB Output is correct
13 Correct 191 ms 28016 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 4 ms 944 KB Output is correct
17 Correct 85 ms 17988 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 45 ms 7148 KB Output is correct
21 Correct 179 ms 27900 KB Output is correct
22 Correct 184 ms 27888 KB Output is correct
23 Correct 185 ms 27984 KB Output is correct
24 Correct 177 ms 27932 KB Output is correct
25 Correct 82 ms 18028 KB Output is correct
26 Correct 78 ms 18004 KB Output is correct
27 Correct 187 ms 27884 KB Output is correct
28 Correct 185 ms 27940 KB Output is correct
29 Correct 1 ms 292 KB Output is correct
30 Correct 1 ms 292 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Incorrect 1 ms 204 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -