oj.uz

Submission #605164

# Submission time Handle Problem Language Result Execution time Memory
605164 2022-07-25T13:35:29 Z alireza_kaviani Airline Route Map (JOI18_airline) C++17
0 / 100
 732 ms 29276 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());
	}
	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 Incorrect 2 ms 4612 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4612 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 29276 KB Output is correct : V - N = 12
2 Correct 485 ms 25656 KB Output is correct : V - N = 12
3 Correct 211 ms 13872 KB Output is correct : V - N = 12
4 Correct 8 ms 5312 KB Output is correct : V - N = 12
5 Correct 117 ms 9912 KB Output is correct : V - N = 12
6 Correct 542 ms 23552 KB Output is correct : V - N = 12
7 Correct 603 ms 28832 KB Output is correct : V - N = 12
8 Correct 668 ms 27364 KB Output is correct : V - N = 12
9 Correct 258 ms 16148 KB Output is correct : V - N = 12
10 Correct 36 ms 6284 KB Output is correct : V - N = 12
11 Correct 48 ms 7420 KB Output is correct : V - N = 12
12 Correct 329 ms 18216 KB Output is correct : V - N = 12
13 Correct 660 ms 28116 KB Output is correct : V - N = 12
14 Correct 541 ms 28552 KB Output is correct : V - N = 12
15 Correct 401 ms 22648 KB Output is correct : V - N = 12
16 Correct 86 ms 8196 KB Output is correct : V - N = 12
17 Correct 20 ms 5680 KB Output is correct : V - N = 12
18 Correct 235 ms 15000 KB Output is correct : V - N = 12
19 Correct 513 ms 26688 KB Output is correct : V - N = 12
20 Correct 724 ms 29100 KB Output is correct : V - N = 12
21 Correct 186 ms 12260 KB Output is correct : V - N = 12
22 Correct 114 ms 10244 KB Output is correct : V - N = 12
23 Correct 59 ms 7316 KB Output is correct : V - N = 12
24 Correct 4 ms 4848 KB Output is correct : V - N = 12
25 Correct 28 ms 6300 KB Output is correct : V - N = 12
26 Incorrect 133 ms 8952 KB Wrong Answer [11]
27 Halted 0 ms 0 KB -