oj.uz

Submission #605167

# Submission time Handle Problem Language Result Execution time Memory
605167 2022-07-25T13:37:23 Z alireza_kaviani Airline Route Map (JOI18_airline) C++17
0 / 100
 680 ms 29236 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

void Alice(int N, int M, int A[], int B[]){
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		E.push_back({A[i] , B[i]});
	}
	for(int i = 0 ; i < N ; i++){
		E.push_back({i , N});
	}
	for(int i = N + 1 ; i < N + LOG ; i++){
		E.push_back({i , i + 1});
	}
	E.push_back({N , N + LOG + 1});
	for(int i = 0 ; i < LOG ; i++){
		for(int j = 0 ; j < N ; j++){
			if((j + 1) & (1 << i)){
				E.push_back({j , N + LOG - i});
			}
		}
	}
	InitG(N + LOG + 2 , SZ(E));
	for(int i = 0 ; i < SZ(E) ; i++){
		MakeG(i , E[i].X , E[i].Y);
	}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y 		second
#define SZ(x)	int((x).size())

const int MAXN = 1510;
const int LOG = 10;

int type[MAXN] , val[MAXN] , ind[MAXN];
vector<int> adj[MAXN] , vec;

void DFS(int v){
	type[v] = 2;
	vec.push_back(v);
	for(int u : adj[v]){
		if(type[u])	continue;
		DFS(u);
	}
}

void Bob(int N, int M, int A[], int B[]){
	int n = N - LOG - 2;
	if(n == 1){
		InitMap(1 , 0);
		return;
	}
	for(int i = 0 ; i < M ; i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	int v = -1;
	for(int i = 0 ; i < N ; i++){
		if(SZ(adj[i]) == 1){
			v = i;
		}
	}
	v = adj[v][0]; type[v] = 3;
	for(int i = 0 ; i < M ; i++){
		if(A[i] == v)	type[B[i]] = 1;
		if(B[i] == v)	type[A[i]] = 1;
	}
	int u = -1;
	for(int i = 0 ; i < N ; i++){
		if(type[i] == 0){
			int cnt = 0;
			for(int j : adj[i]){
				cnt += (type[j] == 0);
			}
			if(cnt == 1){
				u = i;
				break;
			}
		}
	}
	DFS(u);
	if(SZ(adj[vec[0]]) < SZ(adj[vec.back()])){
		reverse(vec.begin() , vec.end());
	}
	assert(SZ(vec) == LOG);
	for(int i = 0 ; i < LOG ; i++){
		val[vec[i]] = i;
		type[vec[i]] = 2;
	}
	vector<pii> E;
	for(int i = 0 ; i < M ; i++){
		if(type[A[i]] > type[B[i]])	swap(A[i] , B[i]);
		if(type[A[i]] == 1 && type[B[i]] == 2){
			ind[A[i]] |= (1 << val[B[i]]);
		}
		if(type[A[i]] == 1 && type[B[i]] == 1){
			E.push_back({A[i] , B[i]});
		}
	}
	InitMap(n , SZ(E));
	for(pii i : E){
		MakeMap(ind[i.X] - 1 , ind[i.Y] - 1);
	}
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4592 KB Output is correct
2 Correct 3 ms 4612 KB Output is correct
3 Correct 3 ms 4616 KB Output is correct
4 Runtime error 4 ms 5888 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4592 KB Output is correct
2 Correct 3 ms 4612 KB Output is correct
3 Correct 3 ms 4616 KB Output is correct
4 Runtime error 4 ms 5888 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 29164 KB Output is correct : V - N = 12
2 Correct 490 ms 25708 KB Output is correct : V - N = 12
3 Correct 166 ms 13796 KB Output is correct : V - N = 12
4 Correct 12 ms 5280 KB Output is correct : V - N = 12
5 Correct 153 ms 9904 KB Output is correct : V - N = 12
6 Correct 422 ms 23592 KB Output is correct : V - N = 12
7 Correct 570 ms 28948 KB Output is correct : V - N = 12
8 Correct 610 ms 27376 KB Output is correct : V - N = 12
9 Correct 358 ms 15972 KB Output is correct : V - N = 12
10 Correct 43 ms 6232 KB Output is correct : V - N = 12
11 Correct 64 ms 7376 KB Output is correct : V - N = 12
12 Correct 313 ms 18084 KB Output is correct : V - N = 12
13 Correct 594 ms 28068 KB Output is correct : V - N = 12
14 Correct 680 ms 28616 KB Output is correct : V - N = 12
15 Correct 415 ms 22528 KB Output is correct : V - N = 12
16 Correct 73 ms 8268 KB Output is correct : V - N = 12
17 Correct 26 ms 5640 KB Output is correct : V - N = 12
18 Correct 224 ms 14988 KB Output is correct : V - N = 12
19 Correct 504 ms 26672 KB Output is correct : V - N = 12
20 Correct 592 ms 29236 KB Output is correct : V - N = 12
21 Correct 198 ms 12212 KB Output is correct : V - N = 12
22 Correct 145 ms 10272 KB Output is correct : V - N = 12
23 Correct 65 ms 7276 KB Output is correct : V - N = 12
24 Correct 4 ms 4868 KB Output is correct : V - N = 12
25 Correct 32 ms 6300 KB Output is correct : V - N = 12
26 Correct 109 ms 9848 KB Output is correct : V - N = 12
27 Correct 164 ms 11220 KB Output is correct : V - N = 12
28 Correct 126 ms 10672 KB Output is correct : V - N = 12
29 Correct 81 ms 7860 KB Output is correct : V - N = 12
30 Runtime error 13 ms 6560 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -