oj.uz

Submission #984305

# Submission time Handle Problem Language Result Execution time Memory
984305 2024-05-16T12:59:53 Z CSQ31 Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 177 ms 32016 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
int p[1000][1000],ans[1000][1000];
void add(int v,int u){
	ans[v][u] = ans[u][v] = 1;
}
int construct(vector<vector<int>> P) {
	int n = sz(P);
	for (int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			p[i][j] = P[i][j];
			if(p[i][j] == 3)return 0;
		}
	}
	//find all nodes connected to 1
	//then nodes with p(1,v) = 1
	//this has to form a tree
	//repeat forming many trees then link the trees in a cycle
	vector<int>ded(n,0);
	for(int i=0;i<n;i++){
		if(ded[i])continue;
		vector<int>comp;
		vector<bool>incomp(n,0);
		for(int j=0;j<n;j++){
			if(ded[j])continue;
			if(p[i][j]){
				incomp[j] = 1;
				comp.push_back(j);
				ded[j] = 1;
			}
		}
		//for(int x:comp)cout<<x<<" ";
		//cout<<'\n';
		vector<vector<int>>trees;
		while(!comp.empty()){
			int v = comp[0];
			vector<int>tree,tmp;
			for(int u:comp){
				if(p[u][v] == 1)tree.push_back(u);
				else tmp.push_back(u);
			}
			trees.push_back(tree);
			comp = tmp;
		}
		int ss = sz(trees);
		if(ss > 1)add(trees[0][0],trees[ss-1][0]);
		for(int i=0;i<ss;i++){
			if(i+1<sz(trees)){
				add(trees[i][0],trees[i+1][0]);
			}
			for(int j=0;j+1<sz(trees[i]);j++){
				add(trees[i][j],trees[i][j+1]);
			}
		}

	}
	vector<vector<int>>fin(n);
	for(int i=0;i<n;i++){
		fin[i].assign(n,0);
		for(int j=0;j<n;j++)fin[i][j] = ans[i][j];
	}
	build(fin);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 7 ms 7624 KB Output is correct
7 Correct 162 ms 31752 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 7 ms 7624 KB Output is correct
7 Correct 162 ms 31752 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 7 ms 5292 KB Output is correct
13 Correct 168 ms 29712 KB Output is correct
14 Incorrect 1 ms 2648 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 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 1 ms 2396 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 41 ms 12620 KB Output is correct
5 Correct 162 ms 31756 KB Output is correct
6 Correct 177 ms 31740 KB Output is correct
7 Correct 169 ms 31880 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 43 ms 12672 KB Output is correct
10 Correct 163 ms 31812 KB Output is correct
11 Correct 167 ms 32016 KB Output is correct
12 Correct 168 ms 31824 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 41 ms 12632 KB Output is correct
17 Correct 162 ms 31872 KB Output is correct
18 Correct 162 ms 31828 KB Output is correct
19 Correct 161 ms 31908 KB Output is correct
20 Correct 164 ms 31744 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 7 ms 7624 KB Output is correct
7 Correct 162 ms 31752 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 7 ms 5292 KB Output is correct
13 Correct 168 ms 29712 KB Output is correct
14 Incorrect 1 ms 2648 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 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 7 ms 7624 KB Output is correct
7 Correct 162 ms 31752 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 7 ms 5292 KB Output is correct
13 Correct 168 ms 29712 KB Output is correct
14 Incorrect 1 ms 2648 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -