| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 51903 |
2018-06-22T14:33:17 Z |
aome |
Simurgh (IOI17_simurgh) |
C++17 |
|
151 ms |
14388 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 510;
int n, m;
int deg[N];
int label[N][N];
bool tree_edge[N][N];
vector<int> res;
vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
n = _n;
if (n == 2) return vector<int>(1, 0);
for (int i = 0; i < n * (n - 1) / 2; ++i) {
label[u[i]][v[i]] = label[v[i]][u[i]] = i;
}
for (int i = 0; i < n; ++i) {
vector<int> ask;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
ask.push_back(label[i][j]);
}
deg[i] = count_common_roads(ask);
}
queue<int> qu;
for (int i = 0; i < n; ++i) {
if (deg[i] == 1) qu.push(i);
}
int leaf1 = qu.front(); qu.pop();
int leaf2 = qu.front();
for (int i = 0; i < n; ++i) {
if (i == leaf1 || i == leaf2) continue;
vector<int> ask;
for (int j = 0; j < n; ++j) {
if (j == leaf1 || j == leaf2) continue;
ask.push_back(label[leaf2][j]);
}
ask.push_back(label[leaf1][i]);
int tmp = count_common_roads(ask);
if (tmp == 2) {
res.push_back(label[leaf1][i]);
tree_edge[leaf1][i] = tree_edge[i][leaf1] = 1;
deg[i]--;
if (deg[i] == 1) qu.push(i);
}
}
while (qu.size()) {
int u = qu.front(); qu.pop();
if (deg[u] != 1) continue;
vector<int> vec;
for (int i = 0; i < n; ++i) {
if (i == leaf1 || i == u) continue;
vec.push_back(i);
}
int l = 0, r = n - 3;
while (l < r) {
int mid = (l + r) >> 1;
vector<int> ask;
int cnt = 0;
for (int i = l; i <= mid; ++i) {
ask.push_back(label[u][vec[i]]);
cnt += tree_edge[u][vec[i]];
}
ask.push_back(label[u][leaf1]);
cnt += tree_edge[u][leaf1];
for (int i = 0; i < l; ++i) {
ask.push_back(label[leaf1][vec[i]]);
cnt += tree_edge[leaf1][vec[i]];
}
for (int i = mid + 1; i < n - 2; ++i) {
ask.push_back(label[leaf1][vec[i]]);
cnt += tree_edge[leaf1][vec[i]];
}
int tmp = count_common_roads(ask);
if (tmp == cnt + 1) r = mid;
else l = mid + 1;
}
res.push_back(label[u][vec[l]]);
tree_edge[u][vec[l]] = tree_edge[vec[l]][u] = 1;
deg[vec[l]]--;
if (deg[vec[l]] == 1) qu.push(vec[l]);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
432 KB |
correct |
| 4 |
Runtime error |
3 ms |
688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
432 KB |
correct |
| 4 |
Runtime error |
3 ms |
688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
432 KB |
correct |
| 4 |
Runtime error |
3 ms |
688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
688 KB |
correct |
| 2 |
Correct |
2 ms |
688 KB |
correct |
| 3 |
Correct |
76 ms |
3068 KB |
correct |
| 4 |
Correct |
115 ms |
4964 KB |
correct |
| 5 |
Correct |
132 ms |
5840 KB |
correct |
| 6 |
Correct |
132 ms |
6800 KB |
correct |
| 7 |
Correct |
151 ms |
7792 KB |
correct |
| 8 |
Correct |
111 ms |
8688 KB |
correct |
| 9 |
Correct |
107 ms |
9612 KB |
correct |
| 10 |
Correct |
117 ms |
10544 KB |
correct |
| 11 |
Correct |
110 ms |
11588 KB |
correct |
| 12 |
Correct |
143 ms |
12576 KB |
correct |
| 13 |
Correct |
2 ms |
12576 KB |
correct |
| 14 |
Correct |
111 ms |
13380 KB |
correct |
| 15 |
Correct |
133 ms |
14388 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
432 KB |
correct |
| 4 |
Runtime error |
3 ms |
688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
