oj.uz

Submission #660397

# Submission time Handle Problem Language Result Execution time Memory
660397 2022-11-21T18:41:43 Z urosk Simurgh (IOI17_simurgh) C++14
13 / 100
 45 ms 16400 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;
    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];
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(n<=7){
        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;
            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 : 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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB correct
2 Correct 45 ms 16260 KB correct
3 Correct 45 ms 16288 KB correct
4 Correct 16 ms 16188 KB correct
5 Correct 16 ms 16212 KB correct
6 Correct 20 ms 16212 KB correct
7 Correct 15 ms 16296 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 18 ms 16172 KB correct
10 Correct 16 ms 16212 KB correct
11 Correct 16 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 45 ms 16264 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB correct
2 Correct 45 ms 16260 KB correct
3 Correct 45 ms 16288 KB correct
4 Correct 16 ms 16188 KB correct
5 Correct 16 ms 16212 KB correct
6 Correct 20 ms 16212 KB correct
7 Correct 15 ms 16296 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 18 ms 16172 KB correct
10 Correct 16 ms 16212 KB correct
11 Correct 16 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 45 ms 16264 KB correct
14 Incorrect 16 ms 16400 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB correct
2 Correct 45 ms 16260 KB correct
3 Correct 45 ms 16288 KB correct
4 Correct 16 ms 16188 KB correct
5 Correct 16 ms 16212 KB correct
6 Correct 20 ms 16212 KB correct
7 Correct 15 ms 16296 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 18 ms 16172 KB correct
10 Correct 16 ms 16212 KB correct
11 Correct 16 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 45 ms 16264 KB correct
14 Incorrect 16 ms 16400 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16212 KB correct
2 Incorrect 17 ms 16212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16212 KB correct
2 Correct 45 ms 16260 KB correct
3 Correct 45 ms 16288 KB correct
4 Correct 16 ms 16188 KB correct
5 Correct 16 ms 16212 KB correct
6 Correct 20 ms 16212 KB correct
7 Correct 15 ms 16296 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 18 ms 16172 KB correct
10 Correct 16 ms 16212 KB correct
11 Correct 16 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 45 ms 16264 KB correct
14 Incorrect 16 ms 16400 KB WA in grader: NO
15 Halted 0 ms 0 KB -