| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626630 |
2022-08-11T15:15:11 Z |
Mounir |
Simurgh (IOI17_simurgh) |
C++14 |
|
164 ms |
9664 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
const int N = 2000;
int ens[N];
int getEns(int noeud){
if (ens[noeud] != noeud)
ens[noeud] = getEns(ens[noeud]);
return ens[noeud];
}
int nNoeuds;
set<int> royales;
vector<pii> aretes;
set<int> sortantes[N];
void findRoyales(int supprime){
for (int noeud = 0; noeud < nNoeuds; ++noeud)
ens[noeud] = noeud;
vector<int> choisies;
int id = -1;
for (pii arete : aretes){
id++;
if (arete.x == supprime || arete.y == supprime) continue;
if (getEns(arete.x) != getEns(arete.y)){
ens[getEns(arete.y)] = getEns(arete.x);
choisies.pb(id);
}
}
vector<pii> resRoute;
for (int sortante : sortantes[supprime]){
choisies.pb(sortante);
resRoute.pb({count_common_roads(choisies), sortante});
choisies.pop_back();
}
sort(all(resRoute));
/* cout << "sup " << supprime << endl;
for (pii a : resRoute)
cout << a.x << " " << a.y << endl;*/
int maxi = resRoute.back().x;
while (!resRoute.empty() && resRoute.back().x == maxi){
royales.insert(resRoute.back().y);
resRoute.pop_back();
}
/*
for (int sortante : sortantes[supprime]){
int autre = aretes[sortante].x;
if (aretes[sortante].x == supprime)
autre = aretes[sortante].y;
sortantes[autre].erase(sortante);
}*/
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
nNoeuds = n;
for (int i = 0; i < sz(u); ++i) {
aretes.pb(make_pair(u[i], v[i]));
sortantes[u[i]].insert(i);
sortantes[v[i]].insert(i);
}
for (int sup = 0; sup < n; ++sup)
findRoyales(sup);
vector<int> ans;
for (int e : royales)
ans.pb(e);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
0 ms |
340 KB |
correct |
| 5 |
Correct |
0 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
0 ms |
340 KB |
correct |
| 9 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
0 ms |
340 KB |
correct |
| 5 |
Correct |
0 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
0 ms |
340 KB |
correct |
| 9 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
0 ms |
340 KB |
correct |
| 5 |
Correct |
0 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
0 ms |
340 KB |
correct |
| 9 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Incorrect |
164 ms |
9664 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
340 KB |
correct |
| 4 |
Correct |
0 ms |
340 KB |
correct |
| 5 |
Correct |
0 ms |
340 KB |
correct |
| 6 |
Correct |
1 ms |
340 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
0 ms |
340 KB |
correct |
| 9 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 10 |
Halted |
0 ms |
0 KB |
- |
