Submission #56088

#	Time	Username	Problem	Language	Result	Execution time	Memory
56088		Benq	Simurgh (IOI17_simurgh)	C++14	100 / 100	715 ms	10596 KiB

simurgh

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
#include "simurgh.h"
 
template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

int N;
vpi ed;
set<int> yes, maybe;
 
//////
/*int sec[500*499/2];
int co;
 
int count_common_roads(vi z) {
    co ++;
    // cout << "HA " << N << " " << sz(z) << "\n";
    assert(sz(z) == N-1);
    DSU<500> D = DSU<500>();
    int ret = 0;
    for (int i: z) {
        if (!D.unite(ed[i].f,ed[i].s)) exit(5);
        if (sec[i]) ret ++;
    }
    return ret;
}*/
//////

vpi ctree;
vpi adj[500];
pi par[500];
int depth[500], status[500*499/2]; // 1 = in, -1 = not

int query(vi x) {
    DSU<500> D; for (int i: x) D.unite(ed[i].f,ed[i].s);
    int ad = 0;
    for (auto a: ctree) if (D.unite(ed[a.f].f,ed[a.f].s)) {
        ad += a.s;
        x.pb(a.f);
    }
    //cout << "OH " << sz(x) << "\n";
    //return 0;
    return count_common_roads(x)-ad;
}

void genDepth(int cur) {
    depth[cur] = depth[par[cur].f]+1;
    for (auto a: adj[cur]) if (a.f != par[cur].f) {
        par[a.f] = {cur,a.s};
        genDepth(a.f);
    }
}

void check(int x) {
    int a = ed[x].f, b = ed[x].s;
    vi tmp = {x};
    bool need = 0;
    while (a != b) {
        if (depth[a] < depth[b]) swap(a,b);
        tmp.pb(par[a].s);
        if (status[par[a].s] == 0) need = 1;
        a = par[a].f;
    }
    if (!need || sz(tmp) == 2) return;
    int mx = -MOD;
    
    for (int i: tmp) if (status[i] != 0) {
        vi v;
        for (int j: tmp) if (j != i) v.pb(j);
        mx = query(v);
        if (status[i] == 1) mx ++;
        break;
    }
    
    vpi TMP;
    for (int i: tmp) if (status[i] == 0) {
        vi v;
        for (int j: tmp) if (j != i) v.pb(j);
        int t = query(v);
        mx = max(mx,t);
        TMP.pb({t,i});
    }
    
    for (auto a: TMP) {
        if (a.f < mx) {
            status[a.s] = 1;
        } else {
            status[a.s] = -1;
        }
    }
}

void addEdge(int x) {
    adj[ed[x].f].pb({ed[x].s,x});
    adj[ed[x].s].pb({ed[x].f,x});
    ctree.pb({x,0});
}

void init() {
    DSU<500> D;
    for (int i: maybe) if (D.unite(ed[i].f,ed[i].s)) addEdge(i);
    genDepth(0);
    for (int i: maybe) check(i);
    for (auto& a: ctree) {
        maybe.erase(a.f);
        if (status[a.f] == 0) status[a.f] = 1;
        a.s = (status[a.f]+1)/2;
        if (a.s) yes.insert(a.f);
        // cout << a.f << " " << a.s << "\n";
    }
    // exit(0);
}

void search(vi x, int num) {
    /*for (int i: x) cout << i << " ";
    cout << "\n";
    cout << num << "\n";*/
    if (num == 0) {
        return;
    }
    if (num == sz(x)) {
        for (int i: x) yes.insert(i);
        return;
    }
    vi X = vi(x.begin(),x.begin()+sz(x)/2);
    int n1 = query(X);
    search(X,n1);
    search(vi(x.begin()+sz(x)/2,x.end()),num-n1);
}
 
vector<int> find_roads(int n, vi u, vi v) {
    yes.clear(), maybe.clear();
    
    N = n;
    ed.resize(sz(u));
    F0R(i,sz(u)) {
        ed[i].f = u[i], ed[i].s = v[i];
        maybe.insert(i);
    }
    
    init();
    
    while (sz(yes) < n-1) {
        DSU<500> D;
        vi tmp;
        for (int x: maybe) if (D.unite(ed[x].f,ed[x].s)) tmp.pb(x);
        for (int x: tmp) maybe.erase(x);
        search(tmp, query(tmp));
    }
    
    vi ans; for (int i: yes) ans.pb(i);
    return ans;
}

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