Submission #55745

#	Time	Username	Problem	Language	Result	Execution time	Memory
55745		Benq	Simurgh (IOI17_simurgh)	C++14	19 / 100	315 ms	15552 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"

int N;
vi U, V;

/*int sec[500*499/2];
int co;

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 count_common_roads(vi z) {
    co ++;
    assert(sz(z) == N-1);
    DSU<500> D = DSU<500>();
    int ret = 0;
    for (int i: z) {
        if (!D.unite(U[i],V[i])) exit(5);
        if (sec[i]) ret ++;
    }
    return ret;
}*/

//////
 

set<int> ctree, adj[500];
int totadj[500], label[500][500], adjsz[500];

void addEdge(int x, int y) {
    ctree.insert(x), ctree.insert(y);
    // cout << "OH " << x << " " << y << "\n";
    adj[x].insert(y), adj[y].insert(x);
}

int get(int x, vi y1, vi y2) {
    set<int> cur; cur.insert(x);
    for (int i: y1) cur.insert(i);
    for (int i: y2) cur.insert(i);
    
    vi edge;
    F0R(i,sz(y1)) {
        edge.pb(label[x][y1[i]]);
        edge.pb(label[y1[i]][y2[i]]);
    }
    
    F0R(i,N) if (!cur.count(i)) edge.pb(label[x][i]);
    return count_common_roads(edge);
}

void search(int x, vi y, int num) {
    if (sz(y) == 1) {
        addEdge(x,y[0]);
        return;
    }
    int q = sz(y)/2;
    vi y1 = vi(y.begin(),y.begin()+q); 
    vi y2 = vi(y.begin()+q,y.begin()+2*q); 
    int t1 = get(x,y1,y2);
    int t2 = get(x,y2,y1);
    if (t1 > t2) {
        search(x,y1,(num+t1-t2)/2);
    } else if (t1 < t2) {
        search(x,y2,(num+t2-t1)/2);
    } else {
        if (num == 1) search(x,{y.back()},1);
        else search(x,y1,num/2);
    }
}

vector<int> find_roads(int n, vi u, vi v) {
    N = n, U = u, V = v;
    F0R(i,sz(u)) label[u[i]][v[i]] = label[v[i]][u[i]] = i;
    ctree.insert(0);
    
    F0R(i,n) {
        vi t;
        F0R(j,n) if (i != j) t.pb(label[i][j]);
        adjsz[i] = count_common_roads(t);
    }
    
    while (sz(ctree) < n) {
        F0R(i,n) if (ctree.count(i) && sz(adj[i]) < adjsz[i]) {
            vi y;
            F0R(j,n) if (!ctree.count(j)) y.pb(j);
            search(i,y,adjsz[i]-sz(adj[i]));
            break;
        }
        //cout << sz(ctree) << "\n";
        //exit(0);
    }
    
    vi ans;
    F0R(i,n) for (int j: adj[i]) if (i < j) ans.pb(label[i][j]);
    return ans;
}

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