oj.uz

Submission #300719

# Submission time Handle Problem Language Result Execution time Memory
300719 2020-09-17T12:38:14 Z Kerim Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 252 ms 22392 KB 
#include "supertrees.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int vis[MAXN];
int construct(std::vector<std::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);
	}int mx=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i!=j)
				umax(mx,p[i][j]);
	if(mx==3)
		return 0;
	if(mx==0){
		build(answer);
		return 1;
	}
	vector<int>a,b; int cnt=0;
	for(int i=0;i<n;i++)
		if(!vis[i]){
			a.clear();b.clear();
			vis[i]=++cnt;a.pb(i);b.pb(i);	
			for(int j=i+1;j<n;j++)
				if(!vis[j] and p[i][j]){
					if(p[i][j]==2)
						a.pb(j);
					else
						b.pb(j),answer[i][j]=answer[j][i]=1;
					vis[j]=cnt;
				}
			for(int j=0;j<int(a.size());j++)
				for(int k=j+1;k<int(a.size());k++)
					if(p[a[j]][a[k]]!=2)
						return 0;
			for(int j=0;j<int(b.size());j++)
				for(int k=j+1;k<int(b.size());k++)
					if(p[b[j]][b[k]]!=1)
						return 0;
		
			for(int j=1;j<int(a.size());j++)
				for(int k=1;k<int(b.size());k++)
					if(p[a[j]][b[k]]!=2)
						return 0;
			if(int(a.size())==1)
				continue;
			if(int(a.size())==2)
				return 0;
			for(int j=0;j<int(a.size());j++)
				answer[a[j]][a[(j+1)%int(a.size())]]=answer[a[(j+1)%int(a.size())]][a[j]]=1;
		}
	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 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 241 ms 22392 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 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 241 ms 22392 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1152 KB Output is correct
13 Correct 252 ms 22136 KB Output is correct
14 Incorrect 1 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 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 10 ms 1152 KB Output is correct
9 Correct 249 ms 22108 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 10 ms 1152 KB Output is correct
13 Correct 242 ms 22136 KB Output is correct
14 Incorrect 1 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 63 ms 5752 KB Output is correct
5 Correct 238 ms 22136 KB Output is correct
6 Correct 235 ms 22136 KB Output is correct
7 Correct 245 ms 22136 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 63 ms 5880 KB Output is correct
10 Correct 243 ms 22136 KB Output is correct
11 Correct 243 ms 22264 KB Output is correct
12 Correct 247 ms 22136 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Incorrect 26 ms 3328 KB Answer gives possible 0 while actual possible 1
17 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 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 241 ms 22392 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1152 KB Output is correct
13 Correct 252 ms 22136 KB Output is correct
14 Incorrect 1 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 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 241 ms 22392 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1152 KB Output is correct
13 Correct 252 ms 22136 KB Output is correct
14 Incorrect 1 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -