oj.uz

Submission #302337

# Submission time Handle Problem Language Result Execution time Memory
302337 2020-09-18T15:48:27 Z TMJN Simurgh (IOI17_simurgh) C++17
19 / 100
 229 ms 4600 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,D[500],ID[500][500];
bool B[500][500];

vector<int>find_roads(int n,vector<int>u,vector<int>v){
	N=n;
	M=u.size();
	assert(M==N*(N-1)/2);
	for(int i=0;i<N;i++){
		D[i]=0;
		for(int j=0;j<N;j++){
			ID[i][j]=B[i][j]=0;
		}
	}
	for(int i=0;i<M;i++){
		ID[u[i]][v[i]]=ID[v[i]][u[i]]=i;
	}
	for(int i=0;i<N;i++){
		vector<int>v;
		for(int j=0;j<N;j++){
			if(i==j)continue;
			v.push_back(ID[i][j]);
		}
		D[i]=count_common_roads(v);
	}
	int uni,K;
	uni=-1;
	K=-1;
	for(int i=0;i<N;i++){
		if(D[i]==1){
			uni=i;
			break;
		}
	}
	for(int i=uni+1;i<N;i++){
		if(D[i]==1){
			vector<int>v;
			for(int j=0;j<N;j++){
				if(j==uni||j==i)continue;
				v.push_back(ID[i][j]);
			}
			v.push_back(-1);
			for(int j=0;j<N;j++){
				if(j==uni)continue;
				if(j==i)continue;
				v.back()=ID[uni][j];
				if(count_common_roads(v)==2){
					K=j;
					break;
				}
			}
			break;
		}
	}
	B[uni][K]=B[K][uni]=true;
	for(int i=0;i<N;i++){
		if(i==uni)continue;
		int last_val=-1;
		for(int j=0;j<D[i]-(i==K);j++){
			int l,r;
			l=last_val;
			r=N-1;
			while(l+1!=r){
				int m=(l+r)/2;
				vector<int>v;
				int c=0;
				v.push_back(ID[uni][i]);
				if(i==K)c=1;
				for(int k=0;k<=last_val;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=m+1;k<N;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=last_val+1;k<=m;k++){
					if(k==uni||k==i)continue;
					v.push_back(ID[i][k]);
				}
				if(count_common_roads(v)>c){
					r=m;
				}
				else{
					l=m;
				}
			}
			B[i][r]=B[r][i]=true;
			last_val=r;
		}
	}
	vector<int>res;
	for(int i=0;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(B[i][j]){
				res.push_back(ID[i][j]);
			}
		}
	}
	return res;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 139 ms 2560 KB correct
4 Correct 217 ms 4480 KB correct
5 Correct 229 ms 4472 KB correct
6 Correct 212 ms 4472 KB correct
7 Correct 209 ms 4472 KB correct
8 Correct 212 ms 4472 KB correct
9 Correct 226 ms 4600 KB correct
10 Correct 222 ms 4476 KB correct
11 Correct 224 ms 4600 KB correct
12 Correct 227 ms 4600 KB correct
13 Correct 1 ms 384 KB correct
14 Correct 222 ms 4600 KB correct
15 Correct 226 ms 4512 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -