oj.uz

Submission #305414

# Submission time Handle Problem Language Result Execution time Memory
305414 2020-09-23T03:14:30 Z diegoangulo5 Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 275 ms 22392 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++){
            int val = p[a][b];
            if(val == 0){
                if(a == b)return 0;
            }
            if(val == 1){
                unir1(a, b);
            }
            if(val == 2){
                if(a == b)return 0;
                unir2(a, b);
            }
        }
    }
    crear2();
    crear1();
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.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 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 275 ms 22264 KB Output is correct

Subtask #2
0 / 10.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 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 275 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 10 ms 1280 KB Output is correct
13 Correct 247 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 1 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 0 ms 256 KB Output is correct
4 Correct 60 ms 5880 KB Output is correct
5 Correct 244 ms 22264 KB Output is correct
6 Correct 234 ms 22212 KB Output is correct
7 Correct 275 ms 22344 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 61 ms 5948 KB Output is correct
10 Correct 236 ms 22264 KB Output is correct
11 Correct 231 ms 22392 KB Output is correct
12 Correct 263 ms 22264 KB Output is correct
13 Correct 0 ms 256 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 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 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 275 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 10 ms 1280 KB Output is correct
13 Correct 247 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 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 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 275 ms 22264 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 10 ms 1280 KB Output is correct
13 Correct 247 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 -