oj.uz

Submission #260432

# Submission time Handle Problem Language Result Execution time Memory
260432 2020-08-10T09:03:05 Z youngyojun Airline Route Map (JOI18_airline) C++17
0 / 100
 1190 ms 30968 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef pair<int, int> pii;
 
static vector<pii> V;
 
void Alice( int N, int M, int A[], int B[] ){
    if(0 == M) exit(-1);
	for(int i = 0; i < M; i++) V.eb(A[i], B[i]);
	for(int i = 0; i < N; i++)
		for(int j = 0; j < 10; j++)
			if(i & (1<<j))
				V.eb(i, N+j);
	for(int i = 0; i < 10; i++) V.eb(N+i, N+10);
	for(int i = 0; i < N+10; i++) V.eb(i, N+11);
	for(int i = 0; i < 9; i++) V.eb(N+i, N+i+1);
 
	InitG(N+12, V.size());
	for(int i = 0; i < V.size(); i++)
		MakeG(i, V[i].first, V[i].second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef pair<int, int> pii;
static void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
 
static const int MAXN = 1055;
 
static vector<int> G[MAXN], CG[MAXN];
static vector<int> VC;
 
static vector<pii> EV;
 
static int D[MAXN];
static bitset<MAXN> isVC;
 
static int N, A, B;
 
void Bob( int V, int U, int C[], int D[] ){
	::N = V-12;
 
	for(int i = 0; i < U; i++) fg(G, C[i], D[i]);
	for(int i = 0; i < V; i++) if(sz(G[i]) == V-2) A = i;
 
	{
		bitset<MAXN> chk;
		for(int v : G[A]) chk[v] = true;
		chk[A] = true;
 
		for(int i = 0; i < V; i++) if(!chk[i]) B = i;
	}
 
	VC = G[B];
	for(int v : VC) isVC[v] = true;
	for(int i = 0; i < U; i++)
		if(isVC[C[i]] && isVC[D[i]])
			fg(CG, C[i], D[i]);
 
	{
		int a = -1, b = -1;
		for(int v : VC) {
			if(1 < sz(CG[v])) continue;
			(a < 0 ? a : b) = v;
		}
 
		if(sz(G[a]) < sz(G[b])) swap(a, b);
 
		vector<int> V; V.eb(a);
		for(int i = CG[a][0]; i != b;) {
			int ta = CG[i][0], tb = CG[i][1];
			ta = ta + tb - V.back();
			V.eb(i);
			i = ta;
		}
		V.eb(b);
 
		VC = V;
	}
 
	for(int i = 0; i < 10; i++)
		for(int v : G[VC[i]])
			::D[v] |= 1<<i;
	::D[A] = ::D[B] = -1;
	for(int v : VC) ::D[v] = -1;
	
	for(int i = 0; i < V; i++) {
		for(int v : G[i]) {
			if(::D[i] < 0 || ::D[v] < 0) continue;
			if(::D[i] < ::D[v]) EV.eb(::D[i], ::D[v]);
		}
	}
 
	InitMap(N, sz(EV));
	for(pii v : EV) MakeMap(v.first, v.second);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < V.size(); i++)
                 ~~^~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6912 KB Output is correct
2 Correct 6 ms 6912 KB Output is correct
3 Correct 7 ms 6912 KB Output is correct
4 Runtime error 4 ms 3328 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6912 KB Output is correct
2 Correct 6 ms 6912 KB Output is correct
3 Correct 7 ms 6912 KB Output is correct
4 Runtime error 4 ms 3328 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 30968 KB Output is correct : V - N = 12
2 Correct 546 ms 26020 KB Output is correct : V - N = 12
3 Correct 208 ms 14312 KB Output is correct : V - N = 12
4 Correct 17 ms 7424 KB Output is correct : V - N = 12
5 Correct 147 ms 11584 KB Output is correct : V - N = 12
6 Correct 758 ms 23932 KB Output is correct : V - N = 12
7 Correct 1190 ms 30504 KB Output is correct : V - N = 12
8 Correct 606 ms 28048 KB Output is correct : V - N = 12
9 Correct 285 ms 17528 KB Output is correct : V - N = 12
10 Correct 43 ms 8424 KB Output is correct : V - N = 12
11 Correct 61 ms 9376 KB Output is correct : V - N = 12
12 Correct 404 ms 19272 KB Output is correct : V - N = 12
13 Correct 649 ms 29320 KB Output is correct : V - N = 12
14 Correct 1109 ms 29864 KB Output is correct : V - N = 12
15 Correct 411 ms 22800 KB Output is correct : V - N = 12
16 Correct 94 ms 10304 KB Output is correct : V - N = 12
17 Correct 27 ms 7888 KB Output is correct : V - N = 12
18 Correct 356 ms 15968 KB Output is correct : V - N = 12
19 Correct 1026 ms 26960 KB Output is correct : V - N = 12
20 Correct 1071 ms 30880 KB Output is correct : V - N = 12
21 Correct 176 ms 13504 KB Output is correct : V - N = 12
22 Correct 246 ms 12088 KB Output is correct : V - N = 12
23 Correct 54 ms 9176 KB Output is correct : V - N = 12
24 Correct 11 ms 6912 KB Output is correct : V - N = 12
25 Correct 27 ms 8432 KB Output is correct : V - N = 12
26 Correct 221 ms 11304 KB Output is correct : V - N = 12
27 Correct 202 ms 13392 KB Output is correct : V - N = 12
28 Correct 161 ms 12792 KB Output is correct : V - N = 12
29 Correct 136 ms 10048 KB Output is correct : V - N = 12
30 Correct 17 ms 7424 KB Output is correct : V - N = 12
31 Runtime error 4 ms 3328 KB Execution failed because the return code was nonzero
32 Halted 0 ms 0 KB -