oj.uz

답안 #302107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302107 2020-09-18T13:01:54 Z TMJN Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 256 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,T[500],val[30000],tmpval[30000];
bool B[30000];
vector<int>U,V,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();
	U=u;
	V=v;
	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);
		}
		val[i]=-1;
		B[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;
		}
		for(int j=0;j<M;j++){
			if(i==j)continue;
			uni(u[j],v[j]);
		}
		vector<int>K;
		for(int j:tree){
			if(i==j)continue;
			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(val[j]!=-1){
					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]))&&val[j]==-1){
					mx=max(mx,tmpval[j]);
				}
			}
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&val[j]==-1){
					if(tmpval[j]==mx){
						B[j]=true;
					}
					val[j]=tmpval[j]+(tmpval[i]==mx);
				}
			}
		}
		else{
			K.back()=t;
			int hoge=count_common_roads(K);
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&val[j]==-1){
					if(tmpval[j]==hoge){
						B[j]=true;
					}
					val[j]=tmpval[j]+(tmpval[i]==hoge);
				}
			}
		}
	}
	for(int i=0;i<M;i++){
		if(B[i])res.push_back(i);
	}
	return res;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB WA in grader: NO
2 Halted 0 ms 0 KB -