oj.uz

Submission #1073541

# Submission time Handle Problem Language Result Execution time Memory
1073541 2024-08-24T15:51:15 Z blushingecchigirl Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 130 ms 24196 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

struct dsu {
    vector<int> parent, rank;
    int size;

    dsu(int sz) {
        size = sz;
        rank.assign(size, 1);
        parent.resize(size);
        for(int i = 0; i<size; i++) parent[i] = i;
    }
    int search(int v) {
        if(v == parent[v]) return v;
        return parent[v] = search(parent[v]);
    }
    void connect(int v, int u) {
        v = search(v);
        u = search(u);
        if(v == u) return;
        if(rank[v]>=rank[u]) parent[u] = v;
        else parent[v] = u;
        if(rank[v] == rank[u]) rank[v]++;
        return;
    }
};

void build(std::vector<std::vector<int>> b);
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	bool ctr = 1;
    vector<vector<int>> b(n);
    for(int i = 0; i<n; i++) b[i].resize(n, 0);
    
    vector<int> a[n];
    dsu d = dsu(n);
    for(int i = 0; i<n; i++) {
        for(int j = 0; j<n; j++) {
            if(p[i][j]) d.connect(i, j);
        }
    }
    for(int i = 0; i<n; i++) {
        a[d.search(i)].pb(i);
    }
    for(int i = 0; i<n; i++) {
        if(a[i].size()<=1) continue;
        vector<int> tree, circle;
        for(int ii:a[i]) {
            bool t1 = 0;
            for(int j:a[i]) {
                if(ii == j) continue;
                if(p[ii][j] == 1) t1 = true;
            }
            if(t1) tree.pb(ii);
            else circle.pb(ii);
        }
        for(size_t ii = 1; ii<tree.size(); ii++) {
            b[tree[ii]][tree[ii-1]] = b[tree[ii-1]][tree[ii]] = 1;
        }
        if(tree.size()) circle.pb(tree[0]);
        for(size_t ii = 1; ii<circle.size(); ii++) {
            b[circle[ii]][circle[ii-1]] = b[circle[ii-1]][circle[ii]] = 1;
        }
        if(circle.size()>1) b[circle[0]][circle.back()] = b[circle.back()][circle[0]] = 1;
    }
	if(ctr) build(b);
	return ctr;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 121 ms 24080 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 121 ms 24080 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 117 ms 24196 KB Output is correct
14 Incorrect 0 ms 348 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 29 ms 6332 KB Output is correct
5 Correct 130 ms 24124 KB Output is correct
6 Correct 114 ms 24148 KB Output is correct
7 Correct 126 ms 23976 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 6196 KB Output is correct
10 Correct 117 ms 24048 KB Output is correct
11 Correct 115 ms 23892 KB Output is correct
12 Correct 124 ms 24148 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 29 ms 6408 KB Too few ways to get from 0 to 24, should be 2 found 1
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 121 ms 24080 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 117 ms 24196 KB Output is correct
14 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 121 ms 24080 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 117 ms 24196 KB Output is correct
14 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -