| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 660411 |
2022-11-21T19:08:18 Z |
urosk |
Simurgh (IOI17_simurgh) |
C++14 |
|
13 ms |
16340 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
#define maxx 250005
vector<ll> g[maxn];
bool ne[maxn],gr[maxx];
ll deg[maxn];
ll m,n;
map<pll,ll> mp;
vector<ll> ans;
bool vis[maxn];
bool tu[maxx];
vector<ll> cur;
bool naso = 0;
void dfs(ll u,ll en,ll bad,ll bad2){
if(u==en){naso = 1;return;}
vis[u] = 1;
for(ll s : g[u]){
if(s==bad2||s==bad||vis[s]||ne[s]||gr[mp[{u,s}]]) continue;
cur.pb(mp[{u,s}]);
tu[cur.back()] = 1;
dfs(s,en,bad,bad2);
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);
if(sz(cur)==n-2) return;
tu[cur.back()] = 0;
cur.popb();
}
}
ll dsu[maxx];
vector<pll> w[maxx];
ll col[maxx];
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[maxx];
ll dfs2(ll u,ll p){
ll sum = 1;
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]||!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;
for(ll i = 1;i<=n;i++) vis[i] = 0;
ll f = dfs2(st,st);
for(ll x : cur) ok[x] = 0;
return f == n;
}
pll c[maxx];
void comb(vector<ll> v,ll i){
if(sz(v)+(m-i+1)<n-1) return;
if(sz(v)==n-1){
if(drvo(v,c[v[0]].fi)&&(calc(v)==n-1)){
for(ll &x : v){
ans.pb(x-1);
}
}
return;
}
if(i==m+1) return;
v.pb(i);
comb(v,i+1);
v.popb();
comb(v,i+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;
}
if(0){
comb({},1);
return ans;
}
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;
if(m==n*(n-1)/2){
set<ll> s;
cur.clear();
s.insert(u[i]);
s.insert(u[j]);
s.insert(v[i]);
s.insert(v[j]);
if(sz(s)==4) continue;
ll x = 0;
if(u[i]==u[j]) x = u[i];
if(u[i]==v[j]) x = u[i];
if(u[j]==u[i]) x = u[j];
if(u[j]==v[i]) x = u[j];
for(ll k = 1;k<=n;k++){
if(s.find(k)!=s.end()) continue;
cur.pb(mp[{x,k}]);
}
s.erase(s.find(x));
auto it = s.begin();
ll a1 = *it;
it++;
ll a2 = *it;
cur.pb(mp[{a1,a2}]);
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);
}else{
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,u[j]^v[j]^en,u[i]^v[i]^st);
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);
if(sz(cur)<n-2) continue;
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 : v2) ans.pb(x);
else if(sz(v2)+sz(ans)!=n-1) for(ll x : v1) ans.pb(x);
else{
for(ll x : v1) ans.pb(x);
bool f = drvo(ans,u[ans[0]]);
if((f&&calc(ans)!=n-1)||(!f)){
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
*/
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:116:9: warning: array subscript 255025 is outside array bounds of 'int [250005]' [-Warray-bounds]
116 | iota(dsu,dsu+maxn*maxn,0);
| ~~~~^~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:56:4: note: while referencing 'dsu'
56 | ll dsu[maxx];
| ^~~
simurgh.cpp:117:9: warning: array subscript 255025 is outside array bounds of 'int [250005]' [-Warray-bounds]
117 | fill(col,col+maxn*maxn,1);
| ~~~~^~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:58:4: note: while referencing 'col'
58 | ll col[maxx];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
16292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
16292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
16292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
16340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
16292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
