oj.uz

Submission #866202

# Submission time Handle Problem Language Result Execution time Memory
866202 2023-10-25T15:21:40 Z lolismek Connecting Supertrees (IOI20_supertrees) C++14
46 / 100
 158 ms 22532 KB 
#include "supertrees.h"
#include <vector>

using namespace std;

const int NMAX = 1000;

vector <int> adj[NMAX + 1];

int par[NMAX + 1];

int Find(int x){
    if(x == par[x]){
        return x;
    }
    return par[x] = Find(par[x]);
}

void Unite(int i, int j){
    i = Find(i);
    j = Find(j);
    par[i] = j;
}

int rep[NMAX + 1];

vector <int> gr[NMAX + 1];

int construct(vector<vector<int>> p) {
	int n = p.size();

    for(int i = 0; i < n; i++){
        par[i] = i;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && p[i][j] == 1 && Find(i) != Find(j)){
                adj[i].push_back(j);
                adj[j].push_back(i);
                Unite(i, j);
            }
            if(p[i][j] == 3){
                return 0;
            }
        }
    }

    for(int i = 0; i < n; i++){
        rep[i] = par[i];
        par[i] = i;
    }



    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 2){
                Unite(rep[i], rep[j]);
            }
        }
    }

    for(int i = 0; i < n; i++){
        gr[Find(i)].push_back(i);
    }

    for(int i = 0; i < n; i++){
        if((int)gr[i].size() >= 3){
            for(int j = 1; j < (int)gr[i].size(); j++){
                adj[gr[i][j]].push_back(gr[i][j - 1]);
                adj[gr[i][j - 1]].push_back(gr[i][j]);
            }
            adj[gr[i].back()].push_back(gr[i][0]);
            adj[gr[i][0]].push_back(gr[i].back());
        }else{
            if((int)gr[i].size() > 1){
                return 0;
            }
        }
    }

    vector <vector <int>> ans(n, vector <int> (n, 0));
    for(int i = 0; i < n; i++){
        for(int x : adj[i]){
            ans[i][x] = 1;
        }
    }

    build(ans);
	return 1;
}

/*
5
1 1 1 2 2
1 1 1 2 2
1 1 1 2 2
2 2 2 1 2
2 2 2 2 1
*/

Subtask #1
11.0 / 11.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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1332 KB Output is correct
7 Correct 139 ms 22532 KB Output is correct

Subtask #2
0 / 10.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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1332 KB Output is correct
7 Correct 139 ms 22532 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 131 ms 22100 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 136 ms 22188 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 143 ms 22176 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 #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 33 ms 5980 KB Output is correct
5 Correct 153 ms 22272 KB Output is correct
6 Correct 135 ms 22076 KB Output is correct
7 Correct 139 ms 22084 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 34 ms 5844 KB Output is correct
10 Correct 138 ms 22100 KB Output is correct
11 Correct 134 ms 22208 KB Output is correct
12 Correct 145 ms 22136 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 34 ms 5808 KB Output is correct
17 Correct 152 ms 22268 KB Output is correct
18 Correct 158 ms 22188 KB Output is correct
19 Correct 137 ms 22060 KB Output is correct
20 Correct 135 ms 22080 KB Output is correct

Subtask #5
0 / 21.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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1332 KB Output is correct
7 Correct 139 ms 22532 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 131 ms 22100 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 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1332 KB Output is correct
7 Correct 139 ms 22532 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 131 ms 22100 KB Output is correct
14 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -