oj.uz

Submission #858137

# Submission time Handle Problem Language Result Execution time Memory
858137 2023-10-07T13:04:52 Z _uros9 Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 211 ms 24232 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int N=1e3+9;
vector<int> rnk(N,0),par(N),rnk1(N,0),par1(N);
int ulp(int node){
    if(par[node]==node) return node;
    return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
    a=ulp(a);b=ulp(b);
    if(a==b) return;
    if(rnk[b]>rnk[a])
        swap(a,b);
    par[b]=a;
    if(rnk[a]==rnk[b])
        rnk[a]++;
}
int ulp1(int node){
    if(par1[node]==node) return node;
    return par1[node]=ulp1(par1[node]);
}
void spajaj1(int a,int b){
    a=ulp1(a);b=ulp1(b);
    if(a==b) return;
    if(rnk1[b]>rnk1[a])
        swap(a,b);
    par1[b]=a;
    if(rnk1[a]==rnk1[b])
        rnk1[a]++;
}

int construct(std::vector<std::vector<int>> p){
	n=p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	vector<set<int>> lanci(n);
	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(p[i][j]==1)
                spajaj(i,j);
            if(p[i][j]==3) return 0;
        }
	}
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==1){
                lanci[ulp(i)].insert(j);
                lanci[ulp(i)].insert(i);
            }
            if(ulp(i)==ulp(j)&&p[i][j]!=1)
                return 0;
        }
	}
	for(int i=0; i<n; i++){
        if(lanci[i].size()<=1) continue;
        for(auto it=next(lanci[i].begin()); it!=lanci[i].end(); it++){
            answer[*prev(it)][*it]=1;
            answer[*it][*prev(it)]=1;
        }
	}
	for(int i=0; i<n; i++) par1[ulp(i)]=ulp(i);
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==2)
                spajaj1(ulp(i),ulp(j));
        }
	}
	vector<set<int>> adj(n);
	for(int i=0; i<n; i++)
        adj[ulp1(i)].insert(ulp(i));
	for(int i=0; i<n; i++){
        if(adj[i].size()<=2) continue;
        for(auto it=next(adj[i].begin()); it!=adj[i].end(); it++){
            answer[*prev(it)][*it]=1;
            answer[*it][*prev(it)]=1;
        }
        answer[*prev(adj[i].end())][*adj[i].begin()]=1;
        answer[*adj[i].begin()][*prev(adj[i].end())]=1;
	}
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==0){
                if(ulp(i)==ulp(j)) return 0;
                if(ulp1(ulp(i))==ulp1(ulp(j))) return 0;
            }
            if(p[i][j]==1)
                if(ulp(i)!=ulp(j)) return 0;
            if(p[i][j]==2){
                if(ulp(i)==ulp(j)) return 0;
                if(ulp1(ulp(i))!=ulp1(ulp(j))) return 0;
            }
        }
	}
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 1372 KB Output is correct
7 Correct 211 ms 23892 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 1372 KB Output is correct
7 Correct 211 ms 23892 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 1372 KB Output is correct
13 Correct 173 ms 24232 KB Output is correct
14 Correct 0 ms 448 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 67 ms 14128 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 45 ms 6944 KB Too many ways to get from 0 to 1, should be 0 found no less than 1
21 Halted 0 ms 0 KB -

Subtask #3
0 / 19.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 344 KB Output is correct
4 Incorrect 1 ms 456 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 44 ms 6420 KB Too many ways to get from 0 to 1, should be 0 found no less than 1
5 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 1372 KB Output is correct
7 Correct 211 ms 23892 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 1372 KB Output is correct
13 Correct 173 ms 24232 KB Output is correct
14 Correct 0 ms 448 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 67 ms 14128 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 45 ms 6944 KB Too many ways to get from 0 to 1, should be 0 found no less than 1
21 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 1372 KB Output is correct
7 Correct 211 ms 23892 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 1372 KB Output is correct
13 Correct 173 ms 24232 KB Output is correct
14 Correct 0 ms 448 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 67 ms 14128 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 45 ms 6944 KB Too many ways to get from 0 to 1, should be 0 found no less than 1
21 Halted 0 ms 0 KB -