Submission #660419

#	Time	Username	Problem	Language	Result	Execution time	Memory
660419		urosk	Simurgh (IOI17_simurgh)	C++14	0 / 100	36 ms	44916 KiB

simurgh

#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*maxn];
bool ne[maxn*maxn],gr[maxx];
ll deg[maxn*maxn];
ll m,n;
map<pll,ll> mp;
vector<ll> ans;
bool vis[maxn*maxn];
bool tu[maxn*maxn];
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[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;
    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[maxn*maxn];
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;
    }
    for(ll i = 1;i<=m;i++) c[i] = {u[i],v[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)!=3) 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(!drvo(cur,c[cur[0]].fi)) continue;
                ll ci = calc(cur);
                cur.popb();
                cur.pb(j);
                if(!drvo(cur,c[cur[0]].fi)) continue;
                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
*/

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30