답안 #835259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835259	2023-08-23T11:18:07 Z	oscar1f	Simurgh (IOI17_simurgh)	C++17	51 / 100	87 ms	4868 KB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"

using namespace std;

const int MAX_SOM=500+5,MAX_ARE=500*500+5;
int nbSom,nbAre,valGlob;
vector<int> debAre,finAre;
vector<pair<int,int>> adja[MAX_SOM];
int prof[MAX_SOM];
int pere[MAX_SOM][2];
int etat[MAX_ARE],pris[MAX_ARE];
vector<int> arbreInit,arcRem,chem,pareil;

void DFS(int pos,int profCour,int anci,int numAre) {
	if (prof[pos]==0) {
		prof[pos]=profCour;
		pere[pos][0]=anci;
		pere[pos][1]=numAre;
		for (auto i:adja[pos]) {
			if (prof[i.first]==0) {
				arbreInit.push_back(i.second);
				DFS(i.first,profCour+1,pos,i.second);
			}
			else if (prof[pos]>prof[i.first]+1) {
				arcRem.push_back(i.second);
			}
		}
	}
}

int askQuest(int nouvAre) {
	vector<int> quest={nouvAre};
	for (int i:arbreInit) {
		if (pris[i]==1) {
			quest.push_back(i);
		}
	}
	return count_common_roads(quest);
}

void afficher(vector<int> v) {
	for (int i:v) {
		cout<<i<<" ";
	}
	cout<<endl;
}

vector<int> find_roads(int n,vector<int> u,vector<int> v) {
	nbSom=n;
	debAre=u;
	finAre=v;
	nbAre=u.size();
	for (int i=0;i<nbAre;i++) {
		adja[debAre[i]].push_back(make_pair(finAre[i],i));
		adja[finAre[i]].push_back(make_pair(debAre[i],i));
	}
	DFS(0,1,0,0);
	//afficher(arbreInit);
	//afficher(arcRem);
	for (int i:arbreInit) {
		pris[i]=1;
	}
	valGlob=count_common_roads(arbreInit);
	int pos,ans;
	for (int i:arcRem) {
		chem.clear();
		if (prof[finAre[i]]<prof[debAre[i]]) {
			swap(finAre[i],debAre[i]);
		}
		pos=finAre[i];
		while (pos!=debAre[i]) {
			chem.push_back(pere[pos][1]);
			pos=pere[pos][0];
		}
		pareil.clear();
		for (int j:chem) {
			if (etat[i]==0 or etat[j]==0) {
				pris[j]=0;
				ans=askQuest(i);
				pris[j]=1;
				if (valGlob<ans) {
					etat[i]=1;
					etat[j]=2;
				}
				else if (valGlob>ans) {
					etat[j]=1;
					etat[i]=2;
				}
				else {
					if (etat[i]==etat[j]) {
						pareil.push_back(j);
					}
					else {
						if (etat[i]==0) {
							etat[i]=etat[j];
						}
						else {
							etat[j]=etat[i];
						}
					}
				}
			}
		}
		if (etat[i]==0) {
			etat[i]=2;
		}
		for (int j:pareil) {
			etat[j]=etat[i];
		}
	}
	vector<int> repOr;
	for (int i=0;i<nbAre;i++) {
		if (etat[i]<=1) {
			repOr.push_back(i);
		}
	}
	return repOr;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	240 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	240 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	2 ms	340 KB	correct
15	Correct	2 ms	340 KB	correct
16	Correct	2 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	340 KB	correct
24	Correct	2 ms	340 KB	correct
25	Correct	1 ms	340 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 KB	correct
29	Correct	1 ms	364 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	380 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	240 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	2 ms	340 KB	correct
15	Correct	2 ms	340 KB	correct
16	Correct	2 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	340 KB	correct
24	Correct	2 ms	340 KB	correct
25	Correct	1 ms	340 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 KB	correct
29	Correct	1 ms	364 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	380 KB	correct
34	Correct	84 ms	1972 KB	correct
35	Correct	81 ms	2132 KB	correct
36	Correct	65 ms	1748 KB	correct
37	Correct	4 ms	340 KB	correct
38	Correct	83 ms	2132 KB	correct
39	Correct	71 ms	2004 KB	correct
40	Correct	56 ms	1748 KB	correct
41	Correct	84 ms	2252 KB	correct
42	Correct	87 ms	2152 KB	correct
43	Correct	44 ms	1536 KB	correct
44	Correct	41 ms	1108 KB	correct
45	Correct	40 ms	1236 KB	correct
46	Correct	32 ms	1140 KB	correct
47	Correct	14 ms	712 KB	correct
48	Correct	1 ms	340 KB	correct
49	Correct	4 ms	456 KB	correct
50	Correct	15 ms	724 KB	correct
51	Correct	44 ms	1260 KB	correct
52	Correct	35 ms	1108 KB	correct
53	Correct	31 ms	980 KB	correct
54	Correct	59 ms	1492 KB	correct
55	Correct	43 ms	1236 KB	correct
56	Correct	42 ms	1172 KB	correct
57	Correct	46 ms	1236 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Incorrect	72 ms	4868 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	0 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	1 ms	240 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	2 ms	340 KB	correct
15	Correct	2 ms	340 KB	correct
16	Correct	2 ms	340 KB	correct
17	Correct	1 ms	340 KB	correct
18	Correct	1 ms	340 KB	correct
19	Correct	1 ms	340 KB	correct
20	Correct	1 ms	340 KB	correct
21	Correct	2 ms	340 KB	correct
22	Correct	1 ms	340 KB	correct
23	Correct	1 ms	340 KB	correct
24	Correct	2 ms	340 KB	correct
25	Correct	1 ms	340 KB	correct
26	Correct	1 ms	340 KB	correct
27	Correct	1 ms	340 KB	correct
28	Correct	1 ms	340 KB	correct
29	Correct	1 ms	364 KB	correct
30	Correct	1 ms	340 KB	correct
31	Correct	1 ms	340 KB	correct
32	Correct	1 ms	340 KB	correct
33	Correct	1 ms	380 KB	correct
34	Correct	84 ms	1972 KB	correct
35	Correct	81 ms	2132 KB	correct
36	Correct	65 ms	1748 KB	correct
37	Correct	4 ms	340 KB	correct
38	Correct	83 ms	2132 KB	correct
39	Correct	71 ms	2004 KB	correct
40	Correct	56 ms	1748 KB	correct
41	Correct	84 ms	2252 KB	correct
42	Correct	87 ms	2152 KB	correct
43	Correct	44 ms	1536 KB	correct
44	Correct	41 ms	1108 KB	correct
45	Correct	40 ms	1236 KB	correct
46	Correct	32 ms	1140 KB	correct
47	Correct	14 ms	712 KB	correct
48	Correct	1 ms	340 KB	correct
49	Correct	4 ms	456 KB	correct
50	Correct	15 ms	724 KB	correct
51	Correct	44 ms	1260 KB	correct
52	Correct	35 ms	1108 KB	correct
53	Correct	31 ms	980 KB	correct
54	Correct	59 ms	1492 KB	correct
55	Correct	43 ms	1236 KB	correct
56	Correct	42 ms	1172 KB	correct
57	Correct	46 ms	1236 KB	correct
58	Correct	1 ms	212 KB	correct
59	Correct	0 ms	212 KB	correct
60	Incorrect	72 ms	4868 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #835259

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0