oj.uz

Submission #835775

# Submission time Handle Problem Language Result Execution time Memory
835775 2023-08-23T19:46:19 Z oscar1f Simurgh (IOI17_simurgh) C++17
100 / 100
 171 ms 7340 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,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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 2 ms 360 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 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 1 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 340 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 340 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 2 ms 360 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 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 1 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 340 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 340 KB correct
34 Correct 28 ms 2208 KB correct
35 Correct 28 ms 2004 KB correct
36 Correct 23 ms 1748 KB correct
37 Correct 7 ms 340 KB correct
38 Correct 28 ms 2004 KB correct
39 Correct 27 ms 1936 KB correct
40 Correct 23 ms 1748 KB correct
41 Correct 28 ms 2056 KB correct
42 Correct 29 ms 2072 KB correct
43 Correct 18 ms 1364 KB correct
44 Correct 15 ms 1108 KB correct
45 Correct 17 ms 1236 KB correct
46 Correct 15 ms 980 KB correct
47 Correct 13 ms 844 KB correct
48 Correct 4 ms 340 KB correct
49 Correct 7 ms 456 KB correct
50 Correct 10 ms 724 KB correct
51 Correct 16 ms 1260 KB correct
52 Correct 15 ms 1108 KB correct
53 Correct 14 ms 980 KB correct
54 Correct 18 ms 1364 KB correct
55 Correct 19 ms 1264 KB correct
56 Correct 20 ms 1236 KB correct
57 Correct 19 ms 1236 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 92 ms 5208 KB correct
4 Correct 155 ms 7168 KB correct
5 Correct 154 ms 7236 KB correct
6 Correct 154 ms 7112 KB correct
7 Correct 154 ms 7280 KB correct
8 Correct 158 ms 7236 KB correct
9 Correct 156 ms 7244 KB correct
10 Correct 154 ms 7236 KB correct
11 Correct 166 ms 7304 KB correct
12 Correct 160 ms 7340 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 159 ms 7240 KB correct
15 Correct 163 ms 7276 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 2 ms 360 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 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 1 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 340 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 340 KB correct
34 Correct 28 ms 2208 KB correct
35 Correct 28 ms 2004 KB correct
36 Correct 23 ms 1748 KB correct
37 Correct 7 ms 340 KB correct
38 Correct 28 ms 2004 KB correct
39 Correct 27 ms 1936 KB correct
40 Correct 23 ms 1748 KB correct
41 Correct 28 ms 2056 KB correct
42 Correct 29 ms 2072 KB correct
43 Correct 18 ms 1364 KB correct
44 Correct 15 ms 1108 KB correct
45 Correct 17 ms 1236 KB correct
46 Correct 15 ms 980 KB correct
47 Correct 13 ms 844 KB correct
48 Correct 4 ms 340 KB correct
49 Correct 7 ms 456 KB correct
50 Correct 10 ms 724 KB correct
51 Correct 16 ms 1260 KB correct
52 Correct 15 ms 1108 KB correct
53 Correct 14 ms 980 KB correct
54 Correct 18 ms 1364 KB correct
55 Correct 19 ms 1264 KB correct
56 Correct 20 ms 1236 KB correct
57 Correct 19 ms 1236 KB correct
58 Correct 1 ms 212 KB correct
59 Correct 1 ms 340 KB correct
60 Correct 92 ms 5208 KB correct
61 Correct 155 ms 7168 KB correct
62 Correct 154 ms 7236 KB correct
63 Correct 154 ms 7112 KB correct
64 Correct 154 ms 7280 KB correct
65 Correct 158 ms 7236 KB correct
66 Correct 156 ms 7244 KB correct
67 Correct 154 ms 7236 KB correct
68 Correct 166 ms 7304 KB correct
69 Correct 160 ms 7340 KB correct
70 Correct 1 ms 212 KB correct
71 Correct 159 ms 7240 KB correct
72 Correct 163 ms 7276 KB correct
73 Correct 1 ms 340 KB correct
74 Correct 153 ms 7244 KB correct
75 Correct 153 ms 7024 KB correct
76 Correct 72 ms 3072 KB correct
77 Correct 164 ms 7280 KB correct
78 Correct 171 ms 7144 KB correct
79 Correct 171 ms 7248 KB correct
80 Correct 158 ms 7148 KB correct
81 Correct 142 ms 6484 KB correct
82 Correct 153 ms 7012 KB correct
83 Correct 103 ms 4248 KB correct
84 Correct 104 ms 5208 KB correct
85 Correct 88 ms 4672 KB correct
86 Correct 68 ms 3280 KB correct
87 Correct 56 ms 2644 KB correct
88 Correct 50 ms 2004 KB correct
89 Correct 49 ms 1996 KB correct
90 Correct 48 ms 1748 KB correct
91 Correct 24 ms 468 KB correct
92 Correct 14 ms 416 KB correct
93 Correct 86 ms 4696 KB correct
94 Correct 69 ms 3280 KB correct
95 Correct 71 ms 3268 KB correct
96 Correct 57 ms 1876 KB correct
97 Correct 49 ms 2048 KB correct
98 Correct 57 ms 2740 KB correct
99 Correct 50 ms 2004 KB correct
100 Correct 32 ms 724 KB correct
101 Correct 15 ms 340 KB correct
102 Correct 103 ms 3928 KB correct
103 Correct 103 ms 3924 KB correct
104 Correct 103 ms 4060 KB correct
105 Correct 103 ms 3924 KB correct