oj.uz

Submission #866208

# Submission time Handle Problem Language Result Execution time Memory
866208 2023-10-25T15:26:13 Z lolismek Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 151 ms 22080 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);
            }else 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){
                if(Find(rep[i]) == Find(rep[j])){
                    return 0;
                }
                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() == 2){
                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 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1368 KB Output is correct
7 Correct 151 ms 22064 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 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 6 ms 1368 KB Output is correct
7 Correct 151 ms 22064 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 1 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 135 ms 22080 KB Output is correct
14 Incorrect 0 ms 344 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 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 344 KB Output is correct
5 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
6 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 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
3 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 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 6 ms 1368 KB Output is correct
7 Correct 151 ms 22064 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 1 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 135 ms 22080 KB Output is correct
14 Incorrect 0 ms 344 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 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 6 ms 1368 KB Output is correct
7 Correct 151 ms 22064 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 1 ms 348 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 135 ms 22080 KB Output is correct
14 Incorrect 0 ms 344 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -