답안 #302123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302123	2020-09-18T13:12:57 Z	TMJN	Simurgh (IOI17_simurgh)	C++17	0 / 100	36 ms	3320 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,T[500],tmpval[30000];
bool B[30000],checked[30000];
vector<int>res,tree;

int par(int x){
	if(T[x]==x)return x;
	return T[x]=par(T[x]);
}

bool uni(int x,int y){
	x=par(x);
	y=par(y);
	if(x==y)return false;
	T[x]=y;
	return true;
}

vector<int>find_roads(int n,vector<int>u,vector<int>v){
	N=n;
	M=u.size();
	for(int i=0;i<N;i++){
		T[i]=i;
	}
	for(int i=0;i<M;i++){
		if(uni(u[i],v[i])){
			tree.push_back(i);
		}
		B[i]=checked[i]=false;
	}
	int tmp=count_common_roads(tree);
	for(int i:tree){
		tmpval[i]=tmp;
	}
	for(int i:tree){
		for(int j=0;j<N;j++){
			T[j]=j;
		}
		vector<int>K;
		for(int j:tree){
			if(i==j)continue;
			uni(u[j],v[j]);
			K.push_back(j);
		}
		K.push_back(-1);
		int t=-1;
		for(int j=0;j<M;j++){
			if(i==j)continue;
			if(par(u[j])!=par(v[j])){
				if(checked[j]){
					if(B[j]){
						t=j;
					}
				}
				else{
					K.back()=j;
					tmpval[j]=count_common_roads(K);
				}
			}
		}
		if(t==-1){
			int mx=0;
			for(int j=0;j<M;j++){
				if(par(u[j]!=par(v[j]))&&!checked[j]){
					mx=max(mx,tmpval[j]);
				}
			}
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&!checked[j]){
					if(tmpval[j]==mx){
						B[j]=true;
					}
					checked[j]=true;
				}
			}
		}
		else{
			K.back()=t;
			int hoge=count_common_roads(K);
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&!checked[j]){
					if(tmpval[j]==hoge){
						B[j]=true;
					}
					checked[j]=true;
				}
			}
		}
	}
	for(int i=0;i<M;i++){
		if(B[i])res.push_back(i);
	}
	return res;
}

Subtask #1

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	correct
2	Correct	0 ms	384 KB	correct
3	Correct	0 ms	384 KB	correct
4	Correct	1 ms	384 KB	correct
5	Correct	0 ms	384 KB	correct
6	Correct	1 ms	384 KB	correct
7	Correct	0 ms	384 KB	correct
8	Correct	0 ms	384 KB	correct
9	Correct	1 ms	256 KB	correct
10	Correct	1 ms	384 KB	correct
11	Correct	0 ms	384 KB	correct
12	Incorrect	0 ms	256 KB	WA in grader: NO
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	correct
2	Correct	0 ms	384 KB	correct
3	Correct	0 ms	384 KB	correct
4	Correct	1 ms	384 KB	correct
5	Correct	0 ms	384 KB	correct
6	Correct	1 ms	384 KB	correct
7	Correct	0 ms	384 KB	correct
8	Correct	0 ms	384 KB	correct
9	Correct	1 ms	256 KB	correct
10	Correct	1 ms	384 KB	correct
11	Correct	0 ms	384 KB	correct
12	Incorrect	0 ms	256 KB	WA in grader: NO
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	correct
2	Correct	0 ms	384 KB	correct
3	Correct	0 ms	384 KB	correct
4	Correct	1 ms	384 KB	correct
5	Correct	0 ms	384 KB	correct
6	Correct	1 ms	384 KB	correct
7	Correct	0 ms	384 KB	correct
8	Correct	0 ms	384 KB	correct
9	Correct	1 ms	256 KB	correct
10	Correct	1 ms	384 KB	correct
11	Correct	0 ms	384 KB	correct
12	Incorrect	0 ms	256 KB	WA in grader: NO
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	256 KB	correct
2	Correct	1 ms	256 KB	correct
3	Runtime error	36 ms	3320 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	correct
2	Correct	0 ms	384 KB	correct
3	Correct	0 ms	384 KB	correct
4	Correct	1 ms	384 KB	correct
5	Correct	0 ms	384 KB	correct
6	Correct	1 ms	384 KB	correct
7	Correct	0 ms	384 KB	correct
8	Correct	0 ms	384 KB	correct
9	Correct	1 ms	256 KB	correct
10	Correct	1 ms	384 KB	correct
11	Correct	0 ms	384 KB	correct
12	Incorrect	0 ms	256 KB	WA in grader: NO
13	Halted	0 ms	0 KB	-