제출 #835259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835259		oscar1f	Simurgh (IOI17_simurgh)	C++17	51 / 100	87 ms	4868 KiB

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30