Submission #70268

#	Time	Username	Problem	Language	Result	Execution time	Memory
70268		top34051	Simurgh (IOI17_simurgh)	C++17	70 / 100	254 ms	8664 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];
int act[maxm], pos[maxm];
vector<int> tree;

vector<pii> way[maxn];
int par[maxn], come[maxn];

vector<int> path;
int rec[maxm];

int res[maxm];

int id[maxn][maxn];

int ask(int last, int id) {
    if(last==-1 || id==-1 || res[last]==-1 || res[id]==-1) {
        return count_common_roads(tree);
    }
    return rec[last] + res[last] - res[id];
}

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

void dfs(int u, int last, int id) {
	par[u] = last; come[u] = id;
	for(auto t : way[u]) {
		int v = t.X, tid = t.Y;
		if(v==last) continue;
		dfs(v,u,tid);
	}
}

void prep(int x, int y) {
	dfs(x,-1,0);
	path.clear();
	for(int i=y;i!=x;i=par[i]) {
//		printf("%d %d : %d\n",par[i],i,come[i]);
		path.push_back(come[i]);
	}
}

vector<int> find_roads4(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
	for(int i=0;i<m;i++) {
		int u = U[i], v = V[i];
		id[u][v] = id[v][u] = i;
	}

	vector<int> vec;
	vec.clear();
	for(int i=0;i<n-1;i++) vec.push_back(id[i][i+1]);
	int ori = count_common_roads(vec);

//	printf("ori = %d\n",ori);

	for(int u=1;u<n-1;u++) {
        vec.clear();
        vec.push_back(id[u-1][u+1]);
        for(int i=0;i<u-1;i++) vec.push_back(id[i][i+1]);
        for(int i=u+1;i<n-1;i++) vec.push_back(id[i][i+1]);
        vec.push_back(-1);
        vec[n-2] = id[u][u+1];
        int tmp1 = count_common_roads(vec);
        vec[n-2] = id[u-1][u];
        int tmp2 = count_common_roads(vec);
//        printf("\tmp1 = %d tmp2 = %d\n",tmp1,tmp2);
        if(ori - tmp1 == 1 || tmp2 - tmp1 == 1) {
//            printf("\t%d - %d = 1\n",u-1,u);
            res[id[u-1][u]] = 1;
        }
        if(ori - tmp2 == 1 || tmp1 - tmp2 == 1) {
//            printf("\t%d - %d = 1\n",u,u+1);
            res[id[u][u+1]] = 1;
        }
        if(tmp1 - ori == 1 || tmp2 - ori == 1) {
//            printf("\t%d - %d = 1\n",u-1,u+1);
            res[id[u-1][u+1]] = 1;
        }
	}

	for(int u=0;u<n;u++) {
        int sz = 0;
        int a[505];
        for(int v=0;v<n;v++) if(v!=u) a[sz++] = v;
        while(1) {
            int l = 0, r = sz-1, x, v = -1;
            while(l<=r) {
                x = (l+r)/2;
                vec.clear();
                int tmp = 0;
                for(int i=0;i<=x;i++) vec.push_back(id[u][a[i]]), tmp -= res[id[u][a[i]]];
                for(int i=x;i<sz-1;i++) vec.push_back(id[a[i]][a[i+1]]), tmp -= res[id[a[i]][a[i+1]]];
//                printf("\task : ");
//                for(auto t : vec) printf("%d ",t);
//                printf("\n");
                tmp += count_common_roads(vec);
                if(tmp >= 1) {
                    v = a[x];
                    r = x-1;
                }
                else l = x+1;
            }
            if(v==-1) break;
//            printf("%d - %d = 1\n",u,v);
            res[id[u][v]] = 1;
        }
	}
	vector<int> ans;
	for(int u=0;u<n;u++) {
        for(int v=u+1;v<n;v++) {
            if(res[id[u][v]]) ans.push_back(id[u][v]);
        }
	}
	return ans;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
    if(m == n*(n-1)/2) return find_roads4(N,U,V);
	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};
		pos[i] = -1;
		if(findhead(u)!=findhead(v)) {
			head[findhead(u)] = findhead(v);
			pos[i] = tree.size();
			tree.push_back(i);
			way[u].push_back({v,i});
			way[v].push_back({u,i});
		}
        res[i] = -1;
	}

	int ori = ask(-1,-1);
//	printf("ori = %d\n",ori);

	for(int i=0;i<m;i++) {
		if(pos[i]!=-1) continue;
		int u = e[i].X, v = e[i].Y;
		prep(u,v);
		int last = -1;
//		printf("edge %d\n",i);
		for(auto id : path) {
			tree[pos[id]] = i;
			rec[id] = ask(last,id);
//			printf("\trec %d = %d\n",id,rec[id]);
			tree[pos[id]] = id;
			last = id;
		}

		res[i] = 0;
		for(auto id : path) {
			if(rec[id]-ori == 1) res[i] = 1;
		}
//		printf("\t\tres = %d\n",res[i]);

		for(auto id : path) {
            res[id] = ori + res[i] - rec[id];
//            printf("\t\tres %d = %d\n",id,res[id]);
		}
	}

	vector<int> vec;
	for(int i=0;i<m;i++) if(res[i]) vec.push_back(i);
//	for(auto t : vec) printf("%d ",t);
	return vec;
}

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