oj.uz

Submission #305410

# Submission time Handle Problem Language Result Execution time Memory
305410 2020-09-23T03:03:43 Z diegoangulo5 Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 293 ms 22396 KB 
#include "supertrees.h"
#include <vector>
#include <set>

using namespace std;

vector< vector<int> > answer;
vector< set<int> >nodos1, nodos2;
vector<int> padre1, padre2, row;
int n;

void init(){
    nodos1.resize(n);
    nodos2.resize(n);
    padre1.resize(n);
    padre2.resize(n);
    row.resize(n);
    for(int a=0;a<n;a++){
        nodos1[a].insert(a);
        nodos2[a].insert(a);
        padre1[a] = a;
        padre2[a] = a;
		answer.push_back(row);
    }
}

set<int> juntar(set<int> a, set<int> b){
    set<int> :: iterator it = b.begin();
    for(;it != b.end();it++){
        a.insert(*it);
    }
    return a;
}

int buscar2(int a){
    if(padre2[a] == a)return a;
    return padre2[a] = buscar2(padre2[a]);
}

void unir2(int a, int b){
    int A = buscar2(a);
    int B = buscar2(b);
    if(A != B){
        padre2[max(A,B)] = min(A,B);
        nodos2[min(A,B)] = juntar(nodos2[A], nodos2[B]);
        nodos2[max(A,B)].clear();
    }
}

int buscar1(int a){
    if(padre1[a] == a)return a;
    return padre1[a] = buscar1(padre1[a]);
}

void unir1(int a, int b){
    int A = buscar1(a);
    int B = buscar1(b);
    if(A != B){
        padre1[max(A,B)] = min(A,B);
        nodos1[min(A,B)] = juntar(nodos1[A], nodos1[B]);
        nodos1[max(A,B)].clear();
    }
}

void crear2(){
    for(int a=0;a<n;a++){
        if(nodos2[a].size() > 1){
            set<int>::iterator it = nodos2[a].begin();
            int anterior = *it;
            it++;
            for(;it != nodos2[a].end();it++){
                answer[anterior][*it] = 1;
                answer[*it][anterior] = 1;
                anterior = *it;
            }
            it--;
            answer[*it][*nodos2[a].begin()] = 1;
            answer[*nodos2[a].begin()][*it] = 1;
        }
    }
}

void crear1(){
    for(int a=0;a<n;a++){
        if(nodos1[a].size() > 1){
            set<int>::iterator it = nodos1[a].begin();
            int anterior = *it;
            it++;
            for(;it != nodos1[a].end();it++){
                answer[anterior][*it] = 1;
                answer[*it][anterior] = 1;
                //anterior = *it;
            }
        }
    }
}

int construct(vector<vector<int> > p) {
	n = p.size();
    init();
    for(int a=0;a<n;a++){
        for(int b=0;b<n;b++){
            if(a == b)continue;
            int val = p[a][b];
            if(val == 1){
                unir1(a, b);
            }
            if(val == 2){
                unir2(a, b);
            }
        }
    }
    crear2();
    crear1();
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 12 ms 1280 KB Output is correct
7 Correct 293 ms 22264 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 12 ms 1280 KB Output is correct
7 Correct 293 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 235 ms 22264 KB Output is correct
14 Incorrect 0 ms 256 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 0 ms 256 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 65 ms 5880 KB Output is correct
5 Correct 246 ms 22264 KB Output is correct
6 Correct 232 ms 22264 KB Output is correct
7 Correct 264 ms 22392 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 61 ms 5880 KB Output is correct
10 Correct 241 ms 22396 KB Output is correct
11 Correct 237 ms 22392 KB Output is correct
12 Correct 270 ms 22392 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Incorrect 0 ms 256 KB Too many ways to get from 0 to 4, should be 1 found no less than 2
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 12 ms 1280 KB Output is correct
7 Correct 293 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 235 ms 22264 KB Output is correct
14 Incorrect 0 ms 256 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 12 ms 1280 KB Output is correct
7 Correct 293 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 235 ms 22264 KB Output is correct
14 Incorrect 0 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -