oj.uz

Submission #689289

# Submission time Handle Problem Language Result Execution time Memory
689289 2023-01-28T05:24:52 Z Sunbae Connecting Supertrees (IOI20_supertrees) C++17
21 / 100
 244 ms 29848 KB 
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> parent, Size;
int findUpar(int node){
    if(node == parent[node]) return node;
    return parent[node] = findUpar(parent[node]);
}
void U(int u, int v){
    int pu = findUpar(u), pv = findUpar(v);
    if(pu == pv) return;
    if(Size[pu] > Size[pv]){
        parent[pv] = pu;
        Size[pu] += Size[pv];
    }else{
        parent[pu] = pv;
        Size[pv] += Size[pu];
    }
}
int construct(vector<vector<int>>p){
    int n = p.size(); parent.resize(n); Size.resize(n);
    for(int i = 0; i<n; i++) parent[i] = i, Size[i] = 1;
    vector<vector<int>>adj(n, vector<int>(n, 0));
    vector<pair<int,int>>zero, two;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(p[i][j] == 0){
                zero.push_back({i, j});
            }else if(p[i][j] == 1){
                U(i, j);
            }else if(p[i][j] == 2){
                two.push_back({i, j});
            }else if(p[i][j] == 3){
                return 0;
            }
        }
    }
    //mark 1
    for(int i = 0; i<n; i++){
        int pi = findUpar(i);
        if(i != pi){
            adj[i][pi] = 1; adj[pi][i] = 1;
        }
    }
    //connect root-root
    set<int>s;
    for(pair<int,int> it: two){
        int pu = findUpar(it.first);
        int pv = findUpar(it.second);
        if(pu == pv) return 0;
        adj[pu][pv] = 1; adj[pv][pu] = 1;
        s.insert(pu);
        s.insert(pv);
    }
    if(s.size() == 2) return 0;
    //making them the same component
    for(pair<int,int> it: two){
        U(findUpar(it.first), findUpar(it.second));
    }
    //check if in the same component (check zero)
    for(pair<int,int> it: zero){
        if(findUpar(it.first) == findUpar(it.second)) return 0;
    }
    build(adj); 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 12 ms 1212 KB Output is correct
7 Correct 178 ms 23892 KB Output is correct

Subtask #2
10.0 / 10.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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 12 ms 1212 KB Output is correct
7 Correct 178 ms 23892 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 212 ms 29792 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 7 ms 1176 KB Output is correct
17 Correct 105 ms 18276 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 51 ms 7656 KB Output is correct
21 Correct 192 ms 29020 KB Output is correct
22 Correct 212 ms 29780 KB Output is correct
23 Correct 206 ms 25844 KB Output is correct
24 Correct 212 ms 29712 KB Output is correct
25 Correct 89 ms 22460 KB Output is correct
26 Correct 86 ms 22412 KB Output is correct
27 Correct 196 ms 25928 KB Output is correct
28 Correct 189 ms 29800 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 204 ms 29848 KB Output is correct
10 Incorrect 1 ms 212 KB Too many ways to get from 0 to 3, should be 2 found no less than 3
11 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 51 ms 7620 KB Output is correct
5 Correct 213 ms 28992 KB Output is correct
6 Correct 244 ms 29752 KB Output is correct
7 Correct 212 ms 25996 KB Output is correct
8 Incorrect 1 ms 212 KB Too many ways to get from 0 to 2, 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 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 12 ms 1212 KB Output is correct
7 Correct 178 ms 23892 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 212 ms 29792 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 7 ms 1176 KB Output is correct
17 Correct 105 ms 18276 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 51 ms 7656 KB Output is correct
21 Correct 192 ms 29020 KB Output is correct
22 Correct 212 ms 29780 KB Output is correct
23 Correct 206 ms 25844 KB Output is correct
24 Correct 212 ms 29712 KB Output is correct
25 Correct 89 ms 22460 KB Output is correct
26 Correct 86 ms 22412 KB Output is correct
27 Correct 196 ms 25928 KB Output is correct
28 Correct 189 ms 29800 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 300 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 8 ms 1492 KB Output is correct
37 Correct 204 ms 29848 KB Output is correct
38 Incorrect 1 ms 212 KB Too many ways to get from 0 to 3, should be 2 found no less than 3
39 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 12 ms 1212 KB Output is correct
7 Correct 178 ms 23892 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 212 ms 29792 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 7 ms 1176 KB Output is correct
17 Correct 105 ms 18276 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 51 ms 7656 KB Output is correct
21 Correct 192 ms 29020 KB Output is correct
22 Correct 212 ms 29780 KB Output is correct
23 Correct 206 ms 25844 KB Output is correct
24 Correct 212 ms 29712 KB Output is correct
25 Correct 89 ms 22460 KB Output is correct
26 Correct 86 ms 22412 KB Output is correct
27 Correct 196 ms 25928 KB Output is correct
28 Correct 189 ms 29800 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 300 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 8 ms 1492 KB Output is correct
37 Correct 204 ms 29848 KB Output is correct
38 Incorrect 1 ms 212 KB Too many ways to get from 0 to 3, should be 2 found no less than 3
39 Halted 0 ms 0 KB -