# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
834671 |
2023-08-22T16:56:10 Z |
merlin |
Simurgh (IOI17_simurgh) |
C++14 |
|
2342 ms |
2900 KB |
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define ll long long
#define f first
#define s second
void setIO(string name="") {
cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
struct dsu{
vector<int> par;
int comps;
dsu(int n){
par = vector<int>(n,-1);
comps = n;
}
int find(int a){
if(par[a] < 0) return a;
par[a] = find(par[a]);
return par[a];
}
void merge(int a,int b){
a = find(a);
b = find(b);
if(a == b) return;
comps--;
if(par[a] > par[b]) swap(a,b);
par[a] += par[b];
par[b] = a;
}
};
vector<vector<pair<int,int>>> sus;
bool dfs(int cur,int par,int target,vector<int> &ret){
if(cur == target) return 1;
for(auto i : sus[cur])if(i.f != par){
if(dfs(i.f,cur,target,ret)){
ret.push_back(i.s);
return 1;
}
}
return 0;
}
int ask(unordered_set<int> a){
vector<int> payload;
for(auto i : a)payload.push_back(i);
return count_common_roads(payload);
}
vector<int> find_roads(int n,vector<int> u,vector<int> v){
assert(n <= 240);
int m = u.size();
vector<int> active(m,1);
vector<int> ans;
while(ans.size() < n-1){
//for(auto i : ans)cerr<<i<<" ";cerr<<endl;
dsu uf(n);
vector<int> teraz = ans;
sus = vector<vector<pair<int,int>>>(n);
for(auto i : ans){
uf.merge(u[i],v[i]);
sus[u[i]].push_back({v[i],i});
sus[v[i]].push_back({u[i],i});
}
int navyse = -1;
for(int i = 0;i<m;i++)if(active[i]){
if(uf.find(u[i]) == uf.find(v[i])){
if(navyse == -1){
navyse = i;
teraz.push_back(i);
//cerr<<"navyse "<<i<<endl;
}
}else{
sus[u[i]].push_back({v[i],i});
sus[v[i]].push_back({u[i],i});
teraz.push_back(i);
//cerr<<i<<endl;
}
uf.merge(u[i],v[i]);
}
if(navyse == -1) return teraz;
vector<int> zaujimave;
dfs(u[navyse],-1,v[navyse],zaujimave);
zaujimave.push_back(navyse);
//for(auto i : zaujimave) cerr<<i<<" ";cerr<<endl;
unordered_set<int> payload;
for(auto i : teraz) payload.insert(i);
vector<int> anss;
int low = 1<<30;
for(auto i : zaujimave){
if(active[i]){
payload.erase(i);
int tmp = ask(payload);
low = min(low,tmp);
anss.push_back(tmp);
payload.insert(i);
}else{
anss.push_back(-1);
}
}
int low_num = 0;
for(int i : anss)if(i <= low) low_num++;
for(int i = 0;i<anss.size();i++){
if(low_num != anss.size() && anss[i] == low && active[zaujimave[i]]){
//cerr<<zaujimave[i]<<" dobra"<<endl;
ans.push_back(zaujimave[i]);
}
active[zaujimave[i]] = 0;
}
}
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:62:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | while(ans.size() < n-1){
| ~~~~~~~~~~~^~~~~
simurgh.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0;i<anss.size();i++){
| ~^~~~~~~~~~~~
simurgh.cpp:111:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if(low_num != anss.size() && anss[i] == low && active[zaujimave[i]]){
| ~~~~~~~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void setIO(std::string)':
simurgh.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | freopen((name+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((name+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
232 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 |
0 ms |
336 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
0 ms |
212 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 |
1 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
232 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 |
0 ms |
336 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
0 ms |
212 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 |
1 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
9 ms |
332 KB |
correct |
15 |
Correct |
12 ms |
340 KB |
correct |
16 |
Correct |
10 ms |
336 KB |
correct |
17 |
Correct |
6 ms |
212 KB |
correct |
18 |
Correct |
2 ms |
212 KB |
correct |
19 |
Correct |
6 ms |
212 KB |
correct |
20 |
Correct |
7 ms |
212 KB |
correct |
21 |
Correct |
6 ms |
224 KB |
correct |
22 |
Correct |
8 ms |
212 KB |
correct |
23 |
Correct |
7 ms |
212 KB |
correct |
24 |
Correct |
7 ms |
212 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
5 ms |
328 KB |
correct |
27 |
Correct |
7 ms |
212 KB |
correct |
28 |
Correct |
3 ms |
212 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
2 ms |
212 KB |
correct |
31 |
Correct |
1 ms |
212 KB |
correct |
32 |
Correct |
2 ms |
336 KB |
correct |
33 |
Correct |
1 ms |
212 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
232 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 |
0 ms |
336 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
0 ms |
212 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 |
1 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
9 ms |
332 KB |
correct |
15 |
Correct |
12 ms |
340 KB |
correct |
16 |
Correct |
10 ms |
336 KB |
correct |
17 |
Correct |
6 ms |
212 KB |
correct |
18 |
Correct |
2 ms |
212 KB |
correct |
19 |
Correct |
6 ms |
212 KB |
correct |
20 |
Correct |
7 ms |
212 KB |
correct |
21 |
Correct |
6 ms |
224 KB |
correct |
22 |
Correct |
8 ms |
212 KB |
correct |
23 |
Correct |
7 ms |
212 KB |
correct |
24 |
Correct |
7 ms |
212 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
5 ms |
328 KB |
correct |
27 |
Correct |
7 ms |
212 KB |
correct |
28 |
Correct |
3 ms |
212 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
2 ms |
212 KB |
correct |
31 |
Correct |
1 ms |
212 KB |
correct |
32 |
Correct |
2 ms |
336 KB |
correct |
33 |
Correct |
1 ms |
212 KB |
correct |
34 |
Correct |
1505 ms |
972 KB |
correct |
35 |
Correct |
1208 ms |
916 KB |
correct |
36 |
Correct |
760 ms |
848 KB |
correct |
37 |
Correct |
28 ms |
340 KB |
correct |
38 |
Correct |
1172 ms |
928 KB |
correct |
39 |
Correct |
1145 ms |
844 KB |
correct |
40 |
Correct |
810 ms |
848 KB |
correct |
41 |
Correct |
2342 ms |
932 KB |
correct |
42 |
Correct |
2258 ms |
928 KB |
correct |
43 |
Correct |
1752 ms |
664 KB |
correct |
44 |
Correct |
1144 ms |
716 KB |
correct |
45 |
Correct |
1497 ms |
664 KB |
correct |
46 |
Correct |
946 ms |
580 KB |
correct |
47 |
Correct |
309 ms |
468 KB |
correct |
48 |
Correct |
11 ms |
384 KB |
correct |
49 |
Correct |
57 ms |
408 KB |
correct |
50 |
Correct |
212 ms |
340 KB |
correct |
51 |
Correct |
1466 ms |
648 KB |
correct |
52 |
Correct |
1083 ms |
604 KB |
correct |
53 |
Correct |
796 ms |
596 KB |
correct |
54 |
Correct |
1649 ms |
668 KB |
correct |
55 |
Correct |
58 ms |
596 KB |
correct |
56 |
Correct |
94 ms |
596 KB |
correct |
57 |
Correct |
103 ms |
640 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
correct |
2 |
Correct |
0 ms |
212 KB |
correct |
3 |
Runtime error |
12 ms |
2900 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
232 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 |
0 ms |
336 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
0 ms |
212 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 |
1 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
9 ms |
332 KB |
correct |
15 |
Correct |
12 ms |
340 KB |
correct |
16 |
Correct |
10 ms |
336 KB |
correct |
17 |
Correct |
6 ms |
212 KB |
correct |
18 |
Correct |
2 ms |
212 KB |
correct |
19 |
Correct |
6 ms |
212 KB |
correct |
20 |
Correct |
7 ms |
212 KB |
correct |
21 |
Correct |
6 ms |
224 KB |
correct |
22 |
Correct |
8 ms |
212 KB |
correct |
23 |
Correct |
7 ms |
212 KB |
correct |
24 |
Correct |
7 ms |
212 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
5 ms |
328 KB |
correct |
27 |
Correct |
7 ms |
212 KB |
correct |
28 |
Correct |
3 ms |
212 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
2 ms |
212 KB |
correct |
31 |
Correct |
1 ms |
212 KB |
correct |
32 |
Correct |
2 ms |
336 KB |
correct |
33 |
Correct |
1 ms |
212 KB |
correct |
34 |
Correct |
1505 ms |
972 KB |
correct |
35 |
Correct |
1208 ms |
916 KB |
correct |
36 |
Correct |
760 ms |
848 KB |
correct |
37 |
Correct |
28 ms |
340 KB |
correct |
38 |
Correct |
1172 ms |
928 KB |
correct |
39 |
Correct |
1145 ms |
844 KB |
correct |
40 |
Correct |
810 ms |
848 KB |
correct |
41 |
Correct |
2342 ms |
932 KB |
correct |
42 |
Correct |
2258 ms |
928 KB |
correct |
43 |
Correct |
1752 ms |
664 KB |
correct |
44 |
Correct |
1144 ms |
716 KB |
correct |
45 |
Correct |
1497 ms |
664 KB |
correct |
46 |
Correct |
946 ms |
580 KB |
correct |
47 |
Correct |
309 ms |
468 KB |
correct |
48 |
Correct |
11 ms |
384 KB |
correct |
49 |
Correct |
57 ms |
408 KB |
correct |
50 |
Correct |
212 ms |
340 KB |
correct |
51 |
Correct |
1466 ms |
648 KB |
correct |
52 |
Correct |
1083 ms |
604 KB |
correct |
53 |
Correct |
796 ms |
596 KB |
correct |
54 |
Correct |
1649 ms |
668 KB |
correct |
55 |
Correct |
58 ms |
596 KB |
correct |
56 |
Correct |
94 ms |
596 KB |
correct |
57 |
Correct |
103 ms |
640 KB |
correct |
58 |
Correct |
0 ms |
212 KB |
correct |
59 |
Correct |
0 ms |
212 KB |
correct |
60 |
Runtime error |
12 ms |
2900 KB |
Execution killed with signal 6 |
61 |
Halted |
0 ms |
0 KB |
- |