# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
834696 |
2023-08-22T17:15:53 Z |
merlin |
Simurgh (IOI17_simurgh) |
C++14 |
|
2433 ms |
2980 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,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.s.s && i.f != par){
if(dfs(i.f,cur,target,ret)){
ret.push_back(i.s.f);
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;
sus = vector<vector<pair<int,pair<int,int>>>>(n);
vector<int> p_u,p_v;
for(int i = 0;i<m;i++){
sus[u[i]].push_back({v[i],{i,0}});
sus[v[i]].push_back({u[i],{i,0}});
p_u.push_back(sus[u[i]].size()-1);
p_v.push_back(sus[v[i]].size()-1);
}
while(ans.size() < n-1){
//for(auto i : ans)cerr<<i<<" ";cerr<<endl;
dsu uf(n);
vector<int> teraz = ans;
for(auto i : ans){
uf.merge(u[i],v[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);
sus[u[i]][p_u[i]].s.s = 1;
sus[v[i]][p_v[i]].s.s = 1;
//cerr<<"navyse "<<i<<endl;
}
}else{
teraz.push_back(i);
sus[u[i]][p_u[i]].s.s = 1;
sus[v[i]][p_v[i]].s.s = 1;
//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]);
}else if(active[zaujimave[i]]){
sus[u[zaujimave[i]]][p_u[zaujimave[i]]].s.s = 0;
sus[v[zaujimave[i]]][p_v[zaujimave[i]]].s.s = 0;
}
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:70:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | while(ans.size() < n-1){
| ~~~~~~~~~~~^~~~~
simurgh.cpp:117:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i = 0;i<anss.size();i++){
| ~^~~~~~~~~~~~
simurgh.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | 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 |
212 KB |
correct |
2 |
Correct |
0 ms |
212 KB |
correct |
3 |
Correct |
0 ms |
212 KB |
correct |
4 |
Correct |
1 ms |
212 KB |
correct |
5 |
Correct |
0 ms |
212 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 |
0 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 |
1 ms |
212 KB |
correct |
5 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
11 ms |
408 KB |
correct |
15 |
Correct |
9 ms |
408 KB |
correct |
16 |
Correct |
8 ms |
408 KB |
correct |
17 |
Correct |
5 ms |
340 KB |
correct |
18 |
Correct |
2 ms |
340 KB |
correct |
19 |
Correct |
5 ms |
340 KB |
correct |
20 |
Correct |
6 ms |
380 KB |
correct |
21 |
Correct |
5 ms |
376 KB |
correct |
22 |
Correct |
5 ms |
340 KB |
correct |
23 |
Correct |
5 ms |
340 KB |
correct |
24 |
Correct |
5 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
4 ms |
340 KB |
correct |
27 |
Correct |
4 ms |
340 KB |
correct |
28 |
Correct |
2 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 |
2 ms |
340 KB |
correct |
33 |
Correct |
1 ms |
340 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 |
1 ms |
212 KB |
correct |
5 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
11 ms |
408 KB |
correct |
15 |
Correct |
9 ms |
408 KB |
correct |
16 |
Correct |
8 ms |
408 KB |
correct |
17 |
Correct |
5 ms |
340 KB |
correct |
18 |
Correct |
2 ms |
340 KB |
correct |
19 |
Correct |
5 ms |
340 KB |
correct |
20 |
Correct |
6 ms |
380 KB |
correct |
21 |
Correct |
5 ms |
376 KB |
correct |
22 |
Correct |
5 ms |
340 KB |
correct |
23 |
Correct |
5 ms |
340 KB |
correct |
24 |
Correct |
5 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
4 ms |
340 KB |
correct |
27 |
Correct |
4 ms |
340 KB |
correct |
28 |
Correct |
2 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 |
2 ms |
340 KB |
correct |
33 |
Correct |
1 ms |
340 KB |
correct |
34 |
Correct |
1521 ms |
2040 KB |
correct |
35 |
Correct |
1207 ms |
2004 KB |
correct |
36 |
Correct |
793 ms |
1764 KB |
correct |
37 |
Correct |
24 ms |
448 KB |
correct |
38 |
Correct |
1165 ms |
2016 KB |
correct |
39 |
Correct |
1181 ms |
1900 KB |
correct |
40 |
Correct |
796 ms |
1756 KB |
correct |
41 |
Correct |
2433 ms |
2028 KB |
correct |
42 |
Correct |
2396 ms |
2004 KB |
correct |
43 |
Correct |
1597 ms |
1364 KB |
correct |
44 |
Correct |
1087 ms |
1108 KB |
correct |
45 |
Correct |
1433 ms |
1148 KB |
correct |
46 |
Correct |
928 ms |
1044 KB |
correct |
47 |
Correct |
241 ms |
680 KB |
correct |
48 |
Correct |
8 ms |
388 KB |
correct |
49 |
Correct |
41 ms |
452 KB |
correct |
50 |
Correct |
183 ms |
596 KB |
correct |
51 |
Correct |
1388 ms |
1164 KB |
correct |
52 |
Correct |
1045 ms |
1108 KB |
correct |
53 |
Correct |
739 ms |
1048 KB |
correct |
54 |
Correct |
1535 ms |
1420 KB |
correct |
55 |
Correct |
59 ms |
1156 KB |
correct |
56 |
Correct |
94 ms |
1156 KB |
correct |
57 |
Correct |
97 ms |
1108 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 |
2980 KB |
Execution killed with signal 6 |
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 |
1 ms |
212 KB |
correct |
5 |
Correct |
0 ms |
212 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 |
0 ms |
212 KB |
correct |
13 |
Correct |
0 ms |
212 KB |
correct |
14 |
Correct |
11 ms |
408 KB |
correct |
15 |
Correct |
9 ms |
408 KB |
correct |
16 |
Correct |
8 ms |
408 KB |
correct |
17 |
Correct |
5 ms |
340 KB |
correct |
18 |
Correct |
2 ms |
340 KB |
correct |
19 |
Correct |
5 ms |
340 KB |
correct |
20 |
Correct |
6 ms |
380 KB |
correct |
21 |
Correct |
5 ms |
376 KB |
correct |
22 |
Correct |
5 ms |
340 KB |
correct |
23 |
Correct |
5 ms |
340 KB |
correct |
24 |
Correct |
5 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
212 KB |
correct |
26 |
Correct |
4 ms |
340 KB |
correct |
27 |
Correct |
4 ms |
340 KB |
correct |
28 |
Correct |
2 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 |
2 ms |
340 KB |
correct |
33 |
Correct |
1 ms |
340 KB |
correct |
34 |
Correct |
1521 ms |
2040 KB |
correct |
35 |
Correct |
1207 ms |
2004 KB |
correct |
36 |
Correct |
793 ms |
1764 KB |
correct |
37 |
Correct |
24 ms |
448 KB |
correct |
38 |
Correct |
1165 ms |
2016 KB |
correct |
39 |
Correct |
1181 ms |
1900 KB |
correct |
40 |
Correct |
796 ms |
1756 KB |
correct |
41 |
Correct |
2433 ms |
2028 KB |
correct |
42 |
Correct |
2396 ms |
2004 KB |
correct |
43 |
Correct |
1597 ms |
1364 KB |
correct |
44 |
Correct |
1087 ms |
1108 KB |
correct |
45 |
Correct |
1433 ms |
1148 KB |
correct |
46 |
Correct |
928 ms |
1044 KB |
correct |
47 |
Correct |
241 ms |
680 KB |
correct |
48 |
Correct |
8 ms |
388 KB |
correct |
49 |
Correct |
41 ms |
452 KB |
correct |
50 |
Correct |
183 ms |
596 KB |
correct |
51 |
Correct |
1388 ms |
1164 KB |
correct |
52 |
Correct |
1045 ms |
1108 KB |
correct |
53 |
Correct |
739 ms |
1048 KB |
correct |
54 |
Correct |
1535 ms |
1420 KB |
correct |
55 |
Correct |
59 ms |
1156 KB |
correct |
56 |
Correct |
94 ms |
1156 KB |
correct |
57 |
Correct |
97 ms |
1108 KB |
correct |
58 |
Correct |
0 ms |
212 KB |
correct |
59 |
Correct |
0 ms |
212 KB |
correct |
60 |
Runtime error |
12 ms |
2980 KB |
Execution killed with signal 6 |
61 |
Halted |
0 ms |
0 KB |
- |