| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1048355 |
2024-08-08T07:02:49 Z |
pcc |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
1628 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;
*/
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 ask(vector<int> &v){
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;
for(auto &i:v)tp[i] = 0;
}
else if(normal>mn){
tp[eid] = 0;
for(auto &i:v)tp[i] = 1;
}
}
else{
assert(mx-mn == 1);
if(mx>normal)tp[eid] = 1;
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;
}
}
return;
}
void solve(int eid){
auto [a,b] = edges[eid];
if(dep[a]>dep[b])swap(a,b);
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;
st.erase(eid);
st.insert(checker);
cerr<<"CHECKER: "<<checker<<','<<re<<endl;
for(auto &i:v){
if(tp[i] == -1){
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;
}
}
}
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<<"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:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:134:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
| ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:141:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
simurgh.cpp:157: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]
157 | for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
correct |
| 2 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1628 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
