| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283733 |
2020-08-26T06:27:09 Z |
erd1 |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
512 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> pii;
typedef long long lld;
typedef long double ld;
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; ++i)
out << (i == b?"":" ") << *i;
return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << '(' << p.ff << ", " << p.ss << ')';
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
return outIt(out << '[', all(v)) << ']';
}
vector<vector<pii>> G;
vector<bool> asked, ans;
vector<int> te, es, dep, par, pe;
vector<pii> qs;
//int c = 0;
void dfs(int i, int d = 1, int p = 0){
//cout << i << " " << d << " " << p << endl;
//if(c++>100)exit(-1);
dep[i] = d;
par[i] = p;
pii minup = {d, -1};
for(auto x : G[i]){
if(x.ss == pe[i])continue;
if(dep[x.ff]){
minup = min(minup, make_pair(dep[x.ff], x.ss));
continue;
}
es.pb(x.ss);
te[x.ss] = es.size();
pe[x.ff] = x.ss;
dfs(x.ff, d + 1, i);
}
if(!i)return;
//cout << i << minup << endl;
if(minup.ff == d){
ans[pe[i]] = true;
asked[pe[i]] = true;
}else{
qs.pb({pe[i], minup.ss});
}
}
int asking(int tree, int nontree){
//cout << "ask " << tree << " " << nontree << endl;
swap(es[te[tree]-1], nontree);
int ansx = count_common_roads(es);
swap(es[te[tree]-1], nontree);
return ansx;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
te.resize(m); asked.resize(m); ans.resize(m); pe.resize(n); par.resize(n); dep.resize(n); pe[0] = -1;
G.resize(n);
for(int i = 0; i < m; i++)G[u[i]].pb({v[i], i}), G[v[i]].pb({u[i], i});
dfs(0);
int tans = count_common_roads(es);
//cout << tans << endl;
//cout << te << es << dep << par << endl;
for(int i = 0; i < m; i++) if(dep[u[i]] < dep[v[i]])swap(u[i], v[i]);
for(int i = 0; i < m; i++)
if(!te[i]){
//cout << i << endl;
for(int c = u[i]; c != v[i]; c = par[c]){
if(asked[pe[c]] && !asked[i]){
int cans = asking(pe[c], i);
if(cans == tans)ans[i] = ans[pe[c]];
//else if(cans < tans)ans[i] = false;
else if(cans > tans)ans[i] = true;
asked[i] = true;
}else if(!asked[pe[c]]){
int cans = asking(pe[c], i);
if(cans < tans)ans[pe[c]] = true;
else if(cans > tans)ans[i] = true;
if(cans != tans) asked[pe[c]] = asked[i] = true;
}
}
assert(asked[i]);
for(int c = u[i]; c != v[i]; c = par[c])
if(!asked[pe[c]])asked[pe[c]] = true, ans[pe[c]] = ans[i];
}
//cout << asked << endl << ans << endl;
vector<int> ret;
for(int i = 0; i < m; i++)if(ans[i])ret.pb(i);
assert(ret.size() == n-1);
return ret;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from simurgh.cpp:3:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:103:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | assert(ret.size() == n-1);
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
