| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 790666 |
2023-07-23T04:58:10 Z |
peteza |
Simurgh (IOI17_simurgh) |
C++14 |
|
72 ms |
3424 KB |
#include "simurgh.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
int ct, ign;
bool vis[505];
vector<pii> adj[505];
vector<int> times[505];
void dfs(int x, vector<int> &to) {
for(pii e:adj[x]) {
if(e.first == ign) {
times[ct].push_back(e.second);
continue;
}
if(vis[e.first]) continue;
vis[e.first] = 1;
to.push_back(e.second);
dfs(e.first, to);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
std::vector<int> r;
int m = u.size();
for(int i=0;i<m;i++) adj[u[i]].emplace_back(v[i], i), adj[v[i]].emplace_back(u[i], i);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) times[j].clear();
//with this node as the main node, generate a spanning tree ignoring this node
ign = i;
std::vector<int> toask;
memset(vis, 0, sizeof vis); vis[i] = 1;
for(int j=0;j<n;j++) {
ct = j;
if(!vis[j]) vis[j] = 1, dfs(j, toask);
}
int cq = 0;
for(int ctime = 0;ctime<n;ctime++) {
if(times[ctime].empty()) continue;
for(int ktime=0;ktime<n;ktime++) {
if(ktime == ctime) continue;
if(times[ktime].size()) toask.push_back(times[ktime][0]);
//for(int e:times[ktime]) toask.push_back(e);
}
std::vector<int> inans;
int mx = -1;
for(int e:times[ctime]) {
toask.push_back(e);
assert(toask.size() == n-1 && cq++ <= 30000);
int res = count_common_roads(toask);
if(res >= mx) {
if(res > mx) inans.clear();
mx = res;
inans.push_back(e);
}
toask.pop_back();
}
for(int ktime=0;ktime<n;ktime++) {
if(ktime == ctime) continue;
if(times[ktime].size()) toask.pop_back();
//for(int e:times[ktime]) toask.pop_back();
}
for(int e:inans) r.push_back(e);
}
}
sort(r.begin(), r.end());
r.resize(unique(r.begin(), r.end())-r.begin());
return r;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from simurgh.cpp:5:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | assert(toask.size() == n-1 && cq++ <= 30000);
| ~~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
0 ms |
276 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
0 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
212 KB |
correct |
| 12 |
Correct |
0 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
0 ms |
276 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
0 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
212 KB |
correct |
| 12 |
Correct |
0 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 KB |
correct |
| 15 |
Correct |
2 ms |
340 KB |
correct |
| 16 |
Correct |
2 ms |
340 KB |
correct |
| 17 |
Correct |
2 ms |
340 KB |
correct |
| 18 |
Correct |
1 ms |
340 KB |
correct |
| 19 |
Correct |
2 ms |
340 KB |
correct |
| 20 |
Correct |
2 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 |
1 ms |
340 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 |
340 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
0 ms |
276 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
0 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
212 KB |
correct |
| 12 |
Correct |
0 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 KB |
correct |
| 15 |
Correct |
2 ms |
340 KB |
correct |
| 16 |
Correct |
2 ms |
340 KB |
correct |
| 17 |
Correct |
2 ms |
340 KB |
correct |
| 18 |
Correct |
1 ms |
340 KB |
correct |
| 19 |
Correct |
2 ms |
340 KB |
correct |
| 20 |
Correct |
2 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 |
1 ms |
340 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 |
340 KB |
correct |
| 34 |
Incorrect |
72 ms |
1364 KB |
WA in grader: NO |
| 35 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
224 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Incorrect |
58 ms |
3424 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
212 KB |
correct |
| 3 |
Correct |
0 ms |
212 KB |
correct |
| 4 |
Correct |
0 ms |
212 KB |
correct |
| 5 |
Correct |
0 ms |
212 KB |
correct |
| 6 |
Correct |
0 ms |
212 KB |
correct |
| 7 |
Correct |
0 ms |
276 KB |
correct |
| 8 |
Correct |
0 ms |
212 KB |
correct |
| 9 |
Correct |
0 ms |
212 KB |
correct |
| 10 |
Correct |
0 ms |
212 KB |
correct |
| 11 |
Correct |
0 ms |
212 KB |
correct |
| 12 |
Correct |
0 ms |
212 KB |
correct |
| 13 |
Correct |
0 ms |
212 KB |
correct |
| 14 |
Correct |
2 ms |
340 KB |
correct |
| 15 |
Correct |
2 ms |
340 KB |
correct |
| 16 |
Correct |
2 ms |
340 KB |
correct |
| 17 |
Correct |
2 ms |
340 KB |
correct |
| 18 |
Correct |
1 ms |
340 KB |
correct |
| 19 |
Correct |
2 ms |
340 KB |
correct |
| 20 |
Correct |
2 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 |
1 ms |
340 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 |
340 KB |
correct |
| 34 |
Incorrect |
72 ms |
1364 KB |
WA in grader: NO |
| 35 |
Halted |
0 ms |
0 KB |
- |
