제출 #835775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835775		oscar1f	Simurgh (IOI17_simurgh)	C++17	100 / 100	171 ms	7340 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,nbQuest=1,verifRest,prevu;
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];
int degRest[MAX_SOM];
int pereUF[MAX_SOM];
vector<int> arbreInit,arcRem,chem,pareil;
vector<int> quest;

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) {
	nbQuest++;
	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;
}

void init() {
    for (int i=0;i<nbSom;i++) {
        pereUF[i]=i;
    }
    quest.clear();
    prevu=0;
}

int find(int pos) {
    if (pereUF[pos]!=pos) {
        pereUF[pos]=find(pereUF[pos]);
    }
    return pereUF[pos];
}

void unir(int idAre,int typeAre) {
    int deb=debAre[idAre],fin=finAre[idAre];
    if (find(deb)!=find(fin)) {
        quest.push_back(idAre);
        pereUF[find(deb)]=find(fin);
        if (typeAre==1 and etat[idAre]==1) {
            prevu++;
        }
    }
}

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=0,ans;
	for (int i:arcRem) {
		chem.clear();
		if (prof[finAre[i]]<prof[debAre[i]]) {
			swap(finAre[i],debAre[i]);
		}
		pos=finAre[i];
        verifRest=0;
		while (pos!=debAre[i]) {
			chem.push_back(pere[pos][1]);
            if (etat[pere[pos][1]]==0) {
                verifRest=1;
            }
			pos=pere[pos][0];
		}
        if (verifRest==1) {
            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];
            }
        }
	}
    for (int i:arbreInit) {
        if (etat[i]==0) {
            etat[i]=1;
        }
        //cout<<i<<" : "<<etat[i]<<endl;
    }
    for (int i=0;i<nbSom;i++) {
        init();
        for (auto j:adja[i]) {
            unir(j.second,0);
        }
        for (int j:arbreInit) {
            unir(j,1);
        }
        ans=count_common_roads(quest);
        nbQuest++;
        degRest[i]=ans-prevu;
        //cout<<i<<" "<<degRest[i]<<endl;
    }
	vector<int> repOr;
    vector<pair<int,int>> nouvVec;
    int deb,fin,mid,nouvAre;
    for (int loop=0;loop<nbSom-1;loop++) {
        for (int i=0;i<nbSom;i++) {
            if (degRest[i]==1) {
                pos=i;
            }
        }
        deb=0;
        fin=adja[pos].size()-1;
        while (deb!=fin) {
            mid=(deb+fin)/2;
            init();
            for (int i=deb;i<=mid;i++) {
                unir(adja[pos][i].second,0);
            }
            for (int j:arbreInit) {
                unir(j,1);
            }
            ans=count_common_roads(quest)-prevu;
            nbQuest++;
            if (ans>=1) {
                fin=mid;
            }
            else {
                deb=mid+1;
            }
        }
        nouvAre=adja[pos][deb].second;
        //cout<<nouvAre<<endl;
        repOr.push_back(nouvAre);
        deb=debAre[nouvAre];
        fin=finAre[nouvAre];
        degRest[deb]--;
        degRest[fin]--;
        nouvVec.clear();
        for (auto j:adja[deb]) {
            if (j!=make_pair(fin,nouvAre)) {
                nouvVec.push_back(j);
            }
        }
        adja[deb]=nouvVec;
        nouvVec.clear();
        for (auto j:adja[fin]) {
            if (j!=make_pair(deb,nouvAre)) {
                nouvVec.push_back(j);
            }
        }
        adja[fin]=nouvVec;
    }
	//cout<<nbQuest<<endl;
	return repOr;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30