| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 597901 |
2022-07-17T05:49:01 Z |
yanndev |
Simurgh (IOI17_simurgh) |
C++17 |
|
32 ms |
7528 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
using namespace std;
const int IDK = 0;
const int NOT_ROYAL = 1;
const int ROYAL = 2;
vector<pair<int, int>> graph[542];
vector<int> back[542];
bool vis[542];
bool dfsTree[4242];
int status[4242];
void dfs(int node, int root, int subId = -1) {
vis[node] = true;
for (auto& x: graph[node]) {
if (vis[x.fi] && x.fi == root)
back[subId].push_back(x.se);
if (!vis[x.fi]) {
int nxtId = subId;
if (subId == -1)
nxtId = x.fi;
dfsTree[x.se] = true;
dfs(x.fi, root, nxtId);
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = (int)u.size();
for (int i = 0; i < m; i++) {
graph[u[i]].push_back({v[i], i});
graph[v[i]].push_back({u[i], i});
}
//printf("n is %d\n", n);
for (int i = 0; i < n; i++) {
//printf("node %d\n", i);
for (int id = 0; id < (int)graph[i].size(); id++) {
auto& x = graph[i][0];
// x.se a royal edge ???
if (status[x.se] != IDK) {
rotate(graph[i].begin(), graph[i].begin() + 1, graph[i].end());
continue;
}
memset(vis, false, sizeof(vis));
memset(dfsTree, false, sizeof(dfsTree));
for (int j = 0; j < n; j++)
back[j].clear();
dfs(i, i, -1);
//printf("is %d\n", x.se);
vector<int> toQ {};
for (int j = 0; j < m; j++) {
if (dfsTree[j] && j != x.se) {
toQ.push_back(j);
//printf("%d ", j);
}
}
//printf("%d\n", x.se);
toQ.push_back(x.se);
int orig = count_common_roads(toQ);
//printf("cnt %d\n", orig);
status[x.se] = ROYAL;
for (auto& y: back[x.fi]) {
if (y == x.se)
continue;
toQ.pop_back();
toQ.push_back(y);
//printf("back %d\n", y);
int newCnt = count_common_roads(toQ);
//printf("new cnt %d\n", newCnt);
/*if (newCnt == orig)
status[x.se] = NOT_ROYAL;*/
if (newCnt > orig) {
status[x.se] = NOT_ROYAL;
status[y] = ROYAL;
}
}
rotate(graph[i].begin(), graph[i].begin() + 1, graph[i].end());
}
//printf("endnode %d\n", i);
}
vector<int> ans {};
for (int i = 0; i < m; i++)
if (status[i] == ROYAL)
ans.push_back(i);
/*printf("ans ");
for (auto& x: ans)
printf("%d ", x);
printf("\n");*/
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
332 KB |
correct |
| 6 |
Correct |
0 ms |
332 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
212 KB |
correct |
| 9 |
Correct |
1 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
328 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
332 KB |
correct |
| 6 |
Correct |
0 ms |
332 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
212 KB |
correct |
| 9 |
Correct |
1 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
328 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
32 ms |
384 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
332 KB |
correct |
| 6 |
Correct |
0 ms |
332 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
212 KB |
correct |
| 9 |
Correct |
1 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
328 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
32 ms |
384 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
328 KB |
correct |
| 3 |
Runtime error |
20 ms |
7528 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
correct |
| 2 |
Correct |
1 ms |
340 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
340 KB |
correct |
| 5 |
Correct |
1 ms |
332 KB |
correct |
| 6 |
Correct |
0 ms |
332 KB |
correct |
| 7 |
Correct |
1 ms |
340 KB |
correct |
| 8 |
Correct |
1 ms |
212 KB |
correct |
| 9 |
Correct |
1 ms |
212 KB |
correct |
| 10 |
Correct |
1 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
328 KB |
correct |
| 12 |
Correct |
1 ms |
340 KB |
correct |
| 13 |
Correct |
1 ms |
340 KB |
correct |
| 14 |
Incorrect |
32 ms |
384 KB |
WA in grader: NO |
| 15 |
Halted |
0 ms |
0 KB |
- |
