제출 #70260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70260		top34051	Simurgh (IOI17_simurgh)	C++17	19 / 100	238 ms	15372 KiB

simurgh

//subtask 4

#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;
int e[maxn][maxn];
int res[maxn][maxn];

vector<int> find_roads(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];
		e[u][v] = e[v][u] = i;
	}

	vector<int> vec;
	vec.clear();
	for(int i=0;i<n-1;i++) vec.push_back(e[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(e[u-1][u+1]);
        for(int i=0;i<u-1;i++) vec.push_back(e[i][i+1]);
        for(int i=u+1;i<n-1;i++) vec.push_back(e[i][i+1]);
        vec.push_back(-1);
        vec[n-2] = e[u][u+1];
        int tmp1 = count_common_roads(vec);
        vec[n-2] = e[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[u-1][u] = res[u][u-1] = 1;
        }
        if(ori - tmp2 == 1 || tmp1 - tmp2 == 1) {
//            printf("\t%d - %d = 1\n",u,u+1);
            res[u][u+1] = res[u+1][u] = 1;
        }
        if(tmp1 - ori == 1 || tmp2 - ori == 1) {
//            printf("\t%d - %d = 1\n",u-1,u+1);
            res[u-1][u+1] = res[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(e[u][a[i]]), tmp -= res[u][a[i]];
                for(int i=x;i<sz-1;i++) vec.push_back(e[a[i]][a[i+1]]), tmp -= res[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[u][v] = res[v][u] = 1;
        }
	}
	vector<int> ans;
	for(int u=0;u<n;u++) {
        for(int v=u+1;v<n;v++) {
            if(res[u][v]) ans.push_back(e[u][v]);
        }
	}
	return ans;
}

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