| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 660385 |
2022-11-21T18:26:41 Z |
urosk |
Simurgh (IOI17_simurgh) |
C++14 |
|
18 ms |
16300 KB |
#include "simurgh.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define here cerr<<"================================\n"
#include <bits/stdc++.h>
#define ll int
#define llinf 1000000000000000000LL
#define pb push_back
#define popb pop_back
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define fi first
#define pll pair<ll,ll>
#define sc second
#define endl '\n'
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 505
vector<ll> g[maxn];
bool ne[maxn],gr[maxn];
ll deg[maxn];
ll m,n;
map<pll,ll> mp;
vector<ll> ans;
bool vis[maxn];
bool tu[maxn];
vector<ll> cur;
bool naso = 0;
void dfs(ll u,ll en){
if(u==en){naso = 1;return;}
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]||ne[s]||gr[mp[{u,s}]]) continue;
cur.pb(mp[{u,s}]);
tu[cur.back()] = 1;
dfs(s,en);
if(naso) return;
tu[cur.back()] = 0;
cur.popb();
}
}
void dfs(ll u){
if(sz(cur)==n-2) return;
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]||ne[s]||gr[mp[{u,s}]]) continue;
cur.pb(mp[{u,s}]);
tu[cur.back()] = 1;
dfs(s,u);
if(sz(cur)==n-2) return;
tu[cur.back()] = 0;
cur.popb();
}
}
ll dsu[maxn*maxn];
vector<pll> w[maxn*maxn];
ll col[maxn*maxn];
ll rut(ll x){
while(x!=dsu[x]) x = dsu[x];
return x;
}
void upd(ll x,ll y,ll e){
e^=col[x]^col[y];
x = rut(x); y = rut(y);
if(x==y) return;
if(sz(w[x])>sz(w[y])) swap(x,y);
dsu[y] = x;
for(pll p : w[y]){
w[x].pb({p.fi,p.sc^e});
col[p.fi] = p.sc^e;
}
}
ll calc(vector<ll> cur){
for(ll &x : cur) x--;
return count_common_roads(cur);
}
bool ok[maxn*maxn];
ll dfs2(ll u,ll p){
ll sum = 1;
for(ll s : g[u]){
if(s==p||!ok[mp[{u,s}]]) continue;
sum+=dfs2(s,u);
}
return sum;
}
bool drvo(vector<ll> cur,ll st){
for(ll x : cur) ok[x] = 1;
ll f = dfs2(st,st);
for(ll x : cur) ok[x] = 0;
return f == n-1;
}
vector<int> find_roads(int N,vector<int> u,vector<int> v) {
n = N;
reverse(all(u)); u.pb(-1); reverse(all(u));
reverse(all(v)); v.pb(-1); reverse(all(v));
iota(dsu,dsu+maxn*maxn,0);
fill(col,col+maxn*maxn,1);
for(ll i = 0;i<maxn*maxn;i++) w[i].pb({i,1});
m = sz(u)-1;
for(ll i = 1;i<=m;i++){
u[i]++; v[i]++;
ll x = u[i],y = v[i];
g[x].pb(y);
g[y].pb(x);
deg[x]++; deg[y]++;
mp[{x,y}] = i;
mp[{y,x}] = i;
}
queue<ll> q;
for(ll i = 1;i<=n;i++) if(deg[i]==1) q.push(i);
while(sz(q)){
ll u = q.front();
ne[u] = 1;
q.pop();
for(ll s : g[u]){
if(ne[s]) continue;
ans.pb(mp[{u,s}]);
gr[mp[{u,s}]] = 1;
deg[s]--;
if(deg[s]==1) q.push(s);
}
}
for(ll i = 1;i<=m;i++){
if(gr[i]) continue;
for(ll j = i+1;j<=m;j++){
if(gr[j]) continue;
if(rut(i)==rut(j)) continue;
for(ll x : cur) tu[x] = 0;
cur.clear();
gr[i] = gr[j] = 1;
ll st = 0,en = 0;
if(u[i]==v[j]||u[i]==u[j]) st = v[i];
else st = u[i];
if(u[j]==v[i]||u[j]==u[i]) en = v[j];
else en = u[j];
naso = 0;
for(ll k = 1;k<=n;k++) vis[k] = 0;
if(u[i]==u[j]||u[i]==v[j]) vis[u[i]] = 1;
if(v[i]==u[j]||v[i]==v[j]) vis[v[i]] = 1;
dfs(st,en);
for(ll k = 1;k<=n;k++) vis[k] = 0;
if(u[i]==u[j]||u[i]==v[j]) vis[u[i]] = 1;
if(v[i]==u[j]||v[i]==v[j]) vis[v[i]] = 1;
for(ll k : cur) vis[u[k]] = vis[v[k]] = 1;
dfs(st);
cur.pb(i);
ll ci = calc(cur);
cur.popb();
cur.pb(j);
ll cj = calc(cur);
ll f = (ci==cj);
upd(i,j,f^1);
gr[i] = gr[j] = 0;
}
}
ll x = 1;
for(ll i = 1;i<=m;i++){
if(gr[i]) continue;
x = rut(i);
}
vector<ll> v1,v2;
for(pll p : w[x]){
if(p.sc) v1.pb(p.fi);
else v2.pb(p.fi);
}
if(sz(v1)+sz(ans)==n-1) for(ll x : v1) ans.pb(x);
else if(sz(v2)+sz(ans)==n-1) for(ll x : v2) ans.pb(x);
else{
for(ll x : v1) ans.pb(x);
if(drvo(ans,u[ans[0]])&&calc(ans)!=n-1){
for(ll i = 0;i<sz(v1);i++) ans.popb();
for(ll x : v2) ans.pb(x);
}
}
for(ll &x : ans) x--;
return ans;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16292 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16292 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16292 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16300 KB |
correct |
| 2 |
Incorrect |
18 ms |
16196 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16292 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
