oj.uz

Submission #835255

# Submission time Handle Problem Language Result Execution time Memory
835255 2023-08-23T11:14:36 Z oscar1f Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 336 KB 
#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];
						}
					}
				}*/
			}
		}
		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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -