oj.uz

Submission #70260

# Submission time Handle Problem Language Result Execution time Memory
70260 2018-08-22T14:19:57 Z top34051 Simurgh (IOI17_simurgh) C++17
19 / 100
 238 ms 15372 KB 
//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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 3 ms 512 KB correct
3 Correct 3 ms 512 KB correct
4 Incorrect 3 ms 512 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 3 ms 512 KB correct
3 Correct 3 ms 512 KB correct
4 Incorrect 3 ms 512 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 3 ms 512 KB correct
3 Correct 3 ms 512 KB correct
4 Incorrect 3 ms 512 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 644 KB correct
2 Correct 3 ms 644 KB correct
3 Correct 118 ms 3992 KB correct
4 Correct 238 ms 6024 KB correct
5 Correct 192 ms 7060 KB correct
6 Correct 238 ms 7916 KB correct
7 Correct 172 ms 8992 KB correct
8 Correct 165 ms 9764 KB correct
9 Correct 182 ms 10656 KB correct
10 Correct 173 ms 11676 KB correct
11 Correct 155 ms 12580 KB correct
12 Correct 166 ms 13504 KB correct
13 Correct 2 ms 13504 KB correct
14 Correct 154 ms 14448 KB correct
15 Correct 163 ms 15372 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 3 ms 512 KB correct
3 Correct 3 ms 512 KB correct
4 Incorrect 3 ms 512 KB WA in grader: NO
5 Halted 0 ms 0 KB -