oj.uz

Submission #896568

# Submission time Handle Problem Language Result Execution time Memory
896568 2024-01-01T17:01:39 Z LCJLY Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 159 ms 22380 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;

struct DSU{
	vector<int>e;
	vector<int>storage[1005];
	void init(int n){
		e=vector<int>(n,-1);
		for(int x=0;x<n;x++){
			storage[x].push_back(x);
		}
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}\
	
	bool sameSet(int x, int y){return get(x)==get(y);}
	
	int size(int x){return -e[get(x)];}
	
	bool unite(int x, int y){
		x=get(x);
		y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		for(auto it:storage[y]) storage[x].push_back(it);
		e[y]=x;
		return 1;
	}
};

int construct(vector<vector<int>> p) {
	//int 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);
	//}
	//build(answer);
	//return 1;

	int n=p.size();
	DSU one;
	one.init(n+5);
	DSU two;
	two.init(n+5);
	
	for(int x=0;x<n;x++){
		for(int y=0;y<n;y++){
			if(p[x][y]==1){
				one.unite(x,y);
			}
			else if(p[x][y]==2){
				two.unite(x,y);
			}
		}
	}
	
	vector<vector<int>>ans;
	ans.resize(n);
	for(int x=0;x<n;x++){
		for(int y=0;y<n;y++){
			ans[x].push_back(0);
		}
	}
	
	bool done[n];
	memset(done,0,sizeof(done));
	for(int x=0;x<n;x++){
		if(one.get(x)==x){
			int last=-1;
			for(auto it:one.storage[x]){
				if(last!=-1){
					ans[last][it]=1;
					ans[it][last]=1;
				}
				else done[it]=true;
				last=it;
			}
		}
	}
	
	for(int x=0;x<n;x++){
		if(two.get(x)==x&&two.size(x)>1){
			if(two.size(x)==2) return 0;
			int last=-1;
			for(auto it:two.storage[x]){
				if(done[it]) continue; 
				if(last!=-1){
					ans[last][it]=1;
					ans[it][last]=1;
				}
				last=it;
			}
			ans[last][two.storage[x][0]]=1;
			ans[two.storage[x][0]][last]=1;
		}
	}
	
	//for(int x=0;x<n;x++){
		//for(int y=0;y<n;y++){
			//if(x==y&&p[x][y]!=1) return 0;
			//if(x==y) continue;
			//if(p[x][y]==0){
				//if(one.sameSet(x,y)||two.sameSet(x,y)) return 0;
			//}
			//else if(p[x][y]==1){
				//if(two.sameSet(x,y)) return 0;
			//}
			//else if(p[x][y]==2){
				//if(one.sameSet(x,y)) return 0;
			//}
		//}	
	//}
	
	build(ans);
	return 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 1372 KB Output is correct
7 Correct 159 ms 22380 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 1372 KB Output is correct
7 Correct 159 ms 22380 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 159 ms 22172 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 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 Runtime error 1 ms 384 KB Execution killed with signal 11
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 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

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 1372 KB Output is correct
7 Correct 159 ms 22380 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 159 ms 22172 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 1372 KB Output is correct
7 Correct 159 ms 22380 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 159 ms 22172 KB Output is correct
14 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -