oj.uz

Submission #302123

# Submission time Handle Problem Language Result Execution time Memory
302123 2020-09-18T13:12:57 Z TMJN Simurgh (IOI17_simurgh) C++17
0 / 100
 36 ms 3320 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -