oj.uz

Submission #660400

# Submission time Handle Problem Language Result Execution time Memory
660400 2022-11-21T18:45:41 Z urosk Simurgh (IOI17_simurgh) C++14
13 / 100
 51 ms 16404 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);
            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
*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16280 KB correct
2 Correct 51 ms 16280 KB correct
3 Correct 45 ms 16212 KB correct
4 Correct 16 ms 16196 KB correct
5 Correct 16 ms 16268 KB correct
6 Correct 19 ms 16212 KB correct
7 Correct 17 ms 16212 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 17 ms 16240 KB correct
10 Correct 17 ms 16300 KB correct
11 Correct 17 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 47 ms 16280 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16280 KB correct
2 Correct 51 ms 16280 KB correct
3 Correct 45 ms 16212 KB correct
4 Correct 16 ms 16196 KB correct
5 Correct 16 ms 16268 KB correct
6 Correct 19 ms 16212 KB correct
7 Correct 17 ms 16212 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 17 ms 16240 KB correct
10 Correct 17 ms 16300 KB correct
11 Correct 17 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 47 ms 16280 KB correct
14 Incorrect 16 ms 16404 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16280 KB correct
2 Correct 51 ms 16280 KB correct
3 Correct 45 ms 16212 KB correct
4 Correct 16 ms 16196 KB correct
5 Correct 16 ms 16268 KB correct
6 Correct 19 ms 16212 KB correct
7 Correct 17 ms 16212 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 17 ms 16240 KB correct
10 Correct 17 ms 16300 KB correct
11 Correct 17 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 47 ms 16280 KB correct
14 Incorrect 16 ms 16404 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16212 KB correct
2 Incorrect 18 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 47 ms 16280 KB correct
2 Correct 51 ms 16280 KB correct
3 Correct 45 ms 16212 KB correct
4 Correct 16 ms 16196 KB correct
5 Correct 16 ms 16268 KB correct
6 Correct 19 ms 16212 KB correct
7 Correct 17 ms 16212 KB correct
8 Correct 16 ms 16212 KB correct
9 Correct 17 ms 16240 KB correct
10 Correct 17 ms 16300 KB correct
11 Correct 17 ms 16212 KB correct
12 Correct 17 ms 16212 KB correct
13 Correct 47 ms 16280 KB correct
14 Incorrect 16 ms 16404 KB WA in grader: NO
15 Halted 0 ms 0 KB -