| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1048702 |
2024-08-08T09:10:19 Z |
pcc |
Simurgh (IOI17_simurgh) |
C++17 |
|
172 ms |
7360 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 550;
pii par[mxn];
vector<pii> paths[mxn];
vector<pii> tree[mxn];
vector<int> back_edge;
int tp[mxn*mxn];
vector<pii> edges;
int dep[mxn];
vector<int> tree_edge;
set<int> tree_st;
int normal = 0;
/*
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
return r;
r[0] = n - 1;
return r;
*/
struct DSU{
int dsu[mxn],sz[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
fill(sz,sz+mxn,1);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a] += sz[b];
dsu[b] = a;
}
};
DSU dsu;
void dfs(int now,int fa){
for(auto &[nxt,id]:paths[now]){
if(nxt == fa)continue;
if(par[nxt].fs == -1){
tree_edge.push_back(id);
par[nxt] = pii(now,id);
dep[nxt] = dep[now]+1;
dfs(nxt,now);
}
else{
back_edge.push_back(id);
}
}
return;
}
int C = 0;
int ask(vector<int> &v){
C++;
assert(C<=30000);
int re = count_common_roads(v);
return re;
}
int ask(set<int> &st){
vector<int> v;
for(auto &i:st)v.push_back(i);
return ask(v);
}
void solve_cycle(vector<int> &v,int eid){
vector<int> res;
auto st = tree_st;
st.insert(eid);
for(auto &i:v){
st.erase(i);
res.push_back(ask(st));
st.insert(i);
}
st.erase(eid);
int mn = *min_element(res.begin(),res.end());
int mx = *max_element(res.begin(),res.end());
//cerr<<"CYCLE: "<<mx<<' '<<mn<<endl;for(auto &i:v)cerr<<i<<',';cerr<<endl;for(auto &i:res)cerr<<i<<',';cerr<<endl;
if(mn == mx){
if(normal == mn){
tp[eid] = 0;
for(auto &i:v)tp[i] = 0;
}
else if(normal<mn){
tp[eid] = 1;dsu.onion(edges[eid].fs,edges[eid].sc);
for(auto &i:v)tp[i] = 0;
}
else if(normal>mn){
tp[eid] = 0;
for(auto &i:v)tp[i] = 1,dsu.onion(edges[i].fs,edges[i].sc);
}
}
else{
assert(mx-mn == 1);
if(mx>normal)tp[eid] = 1,dsu.onion(edges[eid].fs,edges[eid].sc);
else tp[eid] = 0;
for(int i = 0;i<v.size();i++){
if(res[i] == mx)tp[v[i]] = 0;
else tp[v[i]] = 1,dsu.onion(edges[v[i]].fs,edges[v[i]].sc);
}
}
return;
}
void solve(int eid){
auto [a,b] = edges[eid];
if(dep[a]>dep[b])swap(a,b);
if(dsu.root(a) == dsu.root(b)){
tp[eid] = 0;
return;
}
int tmp = b;
vector<int> v;
while(tmp != a){
v.push_back(par[tmp].sc);
tmp = par[tmp].fs;
//cerr<<v.back()<<','<<tmp<<' '<<a<<endl;
}
//cerr<<"SOLVE: "<<eid<<"::";for(auto &i:v)cerr<<i<<',';cerr<<endl;
int checker = -1;
for(auto &i:v){
if(tp[i] != -1)checker = i;
}
if(checker == -1)solve_cycle(v,eid);
else{
auto st = tree_st;
st.erase(checker);
st.insert(eid);
int re = ask(st);
if(re == normal)tp[eid] = tp[checker];
else tp[eid] = tp[checker]^1;
if(tp[eid])dsu.onion(edges[eid].fs,edges[eid].sc);
st.erase(eid);
st.insert(checker);
//cerr<<"CHECKER: "<<checker<<','<<re<<endl;
for(auto &i:v){
if(tp[i] == -1){
auto [a,b] = edges[i];
if(dsu.root(a) == dsu.root(b)){
continue;
}
st.erase(i);
st.insert(eid);
//cerr<<i<<"::";for(auto &j:st)cerr<<j<<',';cerr<<ask(st)<<endl;
if(ask(st) == normal)tp[i] = tp[eid];
else tp[i] = tp[eid]^1;
if(tp[i]){
dsu.onion(a,b);
}
st.insert(i);
st.erase(eid);
}
}
}
//cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
return;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
memset(tp,-1,sizeof(tp));
for(auto &i:par)i = pii(-1,-1);
for(int i = 0;i<u.size();i++){
int a = u[i],b = v[i];
edges.push_back(pii(a,b));
paths[a].push_back(pii(b,i));
paths[b].push_back(pii(a,i));
}
par[0] = pii(0,-1);
dfs(0,0);
sort(back_edge.begin(),back_edge.end());
back_edge.resize(unique(back_edge.begin(),back_edge.end())-back_edge.begin());
for(auto &i:tree_edge)tree_st.insert(i);
//cerr<<"TREE :";for(auto &i:tree_edge)cerr<<i<<',';cerr<<endl;
normal = ask(tree_edge);
//cerr<<"NORMAL: "<<normal<<endl;
for(auto &i:back_edge)solve(i);
vector<int> ans;
for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
//cerr<<C<<" ASKS"<<endl;
//cerr<<"ANS: ";for(auto &i:ans)cerr<<i<<',';cerr<<endl;
return ans;
}
Compilation message
simurgh.cpp: In function 'void solve_cycle(std::vector<int>&, int)':
simurgh.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:178:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
simurgh.cpp:194:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Correct |
0 ms |
1628 KB |
correct |
| 3 |
Correct |
0 ms |
1628 KB |
correct |
| 4 |
Correct |
0 ms |
1628 KB |
correct |
| 5 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Correct |
0 ms |
1628 KB |
correct |
| 3 |
Correct |
0 ms |
1628 KB |
correct |
| 4 |
Correct |
0 ms |
1628 KB |
correct |
| 5 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Correct |
0 ms |
1628 KB |
correct |
| 3 |
Correct |
0 ms |
1628 KB |
correct |
| 4 |
Correct |
0 ms |
1628 KB |
correct |
| 5 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Correct |
1 ms |
1628 KB |
correct |
| 3 |
Incorrect |
172 ms |
7360 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Correct |
0 ms |
1628 KB |
correct |
| 3 |
Correct |
0 ms |
1628 KB |
correct |
| 4 |
Correct |
0 ms |
1628 KB |
correct |
| 5 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
