| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 838182 |
2023-08-26T10:04:13 Z |
Johann |
Simurgh (IOI17_simurgh) |
C++14 |
|
70 ms |
4108 KB |
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N;
vi U, V;
vvpii adj;
vi goldenTree;
const int NOTHING = 0;
const int FRONTIER = 1;
const int EXPLORED = 2;
vi status;
vvi edgesToCandidates;
vi tmpTree;
vi belongs;
int cntQueries;
void buildTree(int v)
{
for (pii e : adj[v])
if (status[e.first] == NOTHING && belongs[e.first] == -1)
{
belongs[e.first] = belongs[v];
tmpTree.push_back(e.second);
buildTree(e.first);
}
else if (status[e.first] == FRONTIER)
edgesToCandidates[belongs[v]].push_back(e.second);
}
void findGoldenTree()
{
if (sz(goldenTree) == N - 1)
return;
int groups = 0;
edgesToCandidates.clear();
tmpTree = vi(all(goldenTree));
belongs.assign(N, -1);
for (int v = 0; v < N; ++v)
if (status[v] == NOTHING && belongs[v] == -1)
{
belongs[v] = groups++;
edgesToCandidates.push_back(vi());
buildTree(v);
assert(!edgesToCandidates.empty());
}
vi toAdd;
for (int g = 0; g < groups; ++g)
{
for (int g2 = 0; g2 < groups; ++g2)
if (g2 != g)
tmpTree.push_back(edgesToCandidates[g2].front());
vi record(sz(edgesToCandidates[g]));
for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
{
tmpTree.push_back(edgesToCandidates[g][i]);
++cntQueries;
// assert(cntQueries <= 30000);
record[i] = count_common_roads(tmpTree);
tmpTree.pop_back();
}
int maxi = *max_element(all(record));
for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
if (maxi == record[i])
toAdd.push_back(edgesToCandidates[g][i]);
for (int g2 = 0; g2 < groups; ++g2)
if (g2 != g)
tmpTree.pop_back();
}
assert(!toAdd.empty());
for (int x : toAdd)
{
if (status[U[x]] != NOTHING)
status[U[x]] = EXPLORED, status[V[x]] = FRONTIER;
else
status[V[x]] = EXPLORED, status[U[x]] = FRONTIER;
goldenTree.push_back(x);
}
findGoldenTree();
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
N = n;
U = u, V = v;
adj = vvpii(n);
for (int i = 0; i < sz(u); ++i)
adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
cntQueries = 0;
goldenTree.clear();
status.assign(n, NOTHING);
status[0] = FRONTIER;
findGoldenTree();
// cout << cntQueries << endl;
return goldenTree;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
212 KB |
correct |
| 6 |
Correct |
1 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
1 ms |
212 KB |
correct |
| 12 |
Correct |
1 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
212 KB |
correct |
| 6 |
Correct |
1 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
1 ms |
212 KB |
correct |
| 12 |
Correct |
1 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 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 |
212 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 |
336 KB |
correct |
| 24 |
Correct |
1 ms |
368 KB |
correct |
| 25 |
Correct |
1 ms |
212 KB |
correct |
| 26 |
Correct |
1 ms |
340 KB |
correct |
| 27 |
Correct |
1 ms |
340 KB |
correct |
| 28 |
Correct |
1 ms |
212 KB |
correct |
| 29 |
Correct |
1 ms |
212 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 |
464 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
212 KB |
correct |
| 6 |
Correct |
1 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
1 ms |
212 KB |
correct |
| 12 |
Correct |
1 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 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 |
212 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 |
336 KB |
correct |
| 24 |
Correct |
1 ms |
368 KB |
correct |
| 25 |
Correct |
1 ms |
212 KB |
correct |
| 26 |
Correct |
1 ms |
340 KB |
correct |
| 27 |
Correct |
1 ms |
340 KB |
correct |
| 28 |
Correct |
1 ms |
212 KB |
correct |
| 29 |
Correct |
1 ms |
212 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 |
464 KB |
correct |
| 34 |
Incorrect |
70 ms |
1664 KB |
WA in grader: NO |
| 35 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
212 KB |
correct |
| 3 |
Incorrect |
54 ms |
4108 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
212 KB |
correct |
| 6 |
Correct |
1 ms |
212 KB |
correct |
| 7 |
Correct |
1 ms |
212 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
1 ms |
212 KB |
correct |
| 12 |
Correct |
1 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 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 |
212 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 |
336 KB |
correct |
| 24 |
Correct |
1 ms |
368 KB |
correct |
| 25 |
Correct |
1 ms |
212 KB |
correct |
| 26 |
Correct |
1 ms |
340 KB |
correct |
| 27 |
Correct |
1 ms |
340 KB |
correct |
| 28 |
Correct |
1 ms |
212 KB |
correct |
| 29 |
Correct |
1 ms |
212 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 |
464 KB |
correct |
| 34 |
Incorrect |
70 ms |
1664 KB |
WA in grader: NO |
| 35 |
Halted |
0 ms |
0 KB |
- |
