Submission #70374

#	Time	Username	Problem	Language	Result	Execution time	Memory
70374		top34051	Simurgh (IOI17_simurgh)	C++17	100 / 100	303 ms	16344 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 500 + 5;
const int maxm = 250000 + 5;

int n,m;
pii e[maxm];

int head[maxn];
vector<pii> way[maxn], edge[maxn];
int ban[maxm], res[maxm];

vector<int> tree;

int h[maxn], par[maxn], rec[maxn];

vector<int> p;
int cut[maxm];

int ask_count;

int ask(int x, int y) {
    for(auto &id : tree) if(id==x) id = y;
    ask_count++;
//    if(ask_count > 8000) assert(0);
    int ret = count_common_roads(tree);
    for(auto &id : tree) if(id==y) id = x;
    return ret;
}

void dfs(int u, int last, int lid) {
    h[u] = h[last] + 1;
    par[u] = last;
    rec[u] = lid;
    for(auto t : way[u]) {
        int v = t.X, id = t.Y;
        if(v==last) continue;
        dfs(v,u,id);
    }
}

void lca(int u, int v) {
    if(u==v) return ;
    if(h[u] >= h[v]) {
        p.push_back(rec[u]);
        lca(par[u],v);
    }
    else lca(v,u);
}

int findhead(int x) {
    if(x==head[x]) return x;
    return head[x] = findhead(head[x]);
}

int get(int x, int l, int r) {
    int val = 0;
    vector<int> vec;
    for(int i=0;i<n;i++) head[i] = i;
    for(int i=l;i<=r;i++) {
        int v = edge[x][i].X, id = edge[x][i].Y;
        head[findhead(x)] = findhead(v);
        vec.push_back(id);
        val -= res[id];
    }
    for(auto id : tree) {
    int u = e[id].X, v = e[id].Y;
        if(findhead(u)!=findhead(v)) {
        head[findhead(u)] = findhead(v);
            vec.push_back(id);
            val -= res[id];
        }
    }
    ask_count++;
    if(ask_count > 8000) assert(0);
    val += count_common_roads(vec);
    return val;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
    for(int i=0;i<n;i++) head[i] = i;
	for(int i=0;i<m;i++) {
		int u = U[i], v = V[i];
        e[i] = {u,v};
        if(findhead(u)!=findhead(v)) {
            head[findhead(u)] = findhead(v);
            way[u].push_back({v,i});
            way[v].push_back({u,i});
            tree.push_back(i);
            ban[i] = 1;
            res[i] = -1;
        }
        else {
            edge[u].push_back({v,i});
            edge[v].push_back({u,i});
        }
	}

    dfs(0,-1,-1);

    int ori = ask(-1,-1);
    for(int i=0;i<m;i++) {
        if(ban[i]) continue;
        int u = e[i].X, v = e[i].Y, wow = i;

        p.clear();
        lca(u,v);

        int good = 0;
        for(auto id : p) if(res[id]==-1) good = 1;
        if(!good) continue;

        int x = -1;
        for(auto id : p) if(res[id]!=-1) x = id;
        if(x==-1) {
            for(auto id : p) cut[id] = ask(id,wow);
            for(auto id : p) if(cut[id] - ori == 1) res[wow] = 1;
            for(auto id : p) res[id] = ori - cut[id] + res[wow];
        }
        else {
            res[wow] = ask(x,wow) - ori + res[x];
            for(auto id : p) if(res[id]==-1) res[id] = ori - ask(id,wow) + res[wow];
        }
    }
    for(int i=0;i<m;i++) {
        if(res[i] == -1) res[i] = 1;
//        if(ban[i]) printf("%d %d : %d\n",e[i].X,e[i].Y,res[i]);
    }

    for(int x=0;x<n;x++) {
//        printf("x = %d : ask count = %d\n",x,ask_count);
        for(int ext=get(x,0,edge[x].size()-1);ext>0;ext--) {
            int l = 0, r = edge[x].size()-1, mid, pos = -1;
            while(l<=r) {
                mid = (l+r)/2;
                if(get(x,0,mid) >= 1) {
                    pos = edge[x][mid].Y;
                    r = mid-1;
                }
                else l = mid+1;
            }
            if(pos==-1) break;
            res[pos] = 1;
//            printf("\tedge %d %d is good\n",e[pos].X,e[pos].Y);
        }
    }

    vector<int> ans;
    for(int i=0;i<m;i++) if(res[i]) ans.push_back(i);
    return ans;
}

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