oj.uz

Submission #331850

# Submission time Handle Problem Language Result Execution time Memory
331850 2020-11-30T12:25:17 Z pit4h Airline Route Map (JOI18_airline) C++14
0 / 100
 893 ms 29668 KB 
#include<bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define st first
#define nd second
#define mp make_pair
using pii = pair<int, int>;
const int MAXN = 1020, MAXB = 10;
int deg[MAXN];
vector<pii> edge;
void Alice( int N, int M, int A[], int B[] ){
	for(int i=0; i<M; ++i) {
		A[i]++; B[i]++;
		edge.push_back(mp(A[i], B[i]));
		deg[A[i]]++;
		deg[B[i]]++;
		A[i]--;
		B[i]--;
	}
	for(int i=1; i<=N; ++i) {
		if(!deg[i]) continue;
		for(int j=0; j<MAXB; ++j) {
			if((1<<j)&i) {
				edge.push_back(mp(i, N+1+j));
			}
		}
	}
	for(int i=0; i<MAXB; ++i) {
		edge.push_back(mp(N+MAXB+1, N+i+1));
	}
	for(int i=0; i<MAXB/2; ++i) {
		for(int j=MAXB-1; j>=MAXB-1-i; --j) {
			edge.push_back(mp(N+i+1, N+j+1));
		}
	}
	edge.push_back(mp(N+MAXB+2, N+MAXB+1));

	InitG(N+MAXB+2, edge.size());
	for(int i=0; i<(int)edge.size(); ++i) {
		MakeG(i, edge[i].st-1, edge[i].nd-1);
		//cerr<<edge[i].st<<' '<<edge[i].nd<<'\n';
	}
}


#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
using pii = pair<int, int>;
const int MAXN = 1020, MAXB = 10;
int N;
int root, bits[MAXN], first_bit, mid_bit, id[MAXN];
bool node[MAXN], is_bit[MAXN], sec_half[MAXN];
vector<int> g[MAXN], gb[MAXN];
vector<pii> edges;

void Bob( int V, int U, int C[], int D[] ){
	N = V - (MAXB+2);
	for(int i=0; i<U; ++i) {
		g[C[i]].push_back(D[i]);
		g[D[i]].push_back(C[i]);
	}
	for(int i=0; i<V; ++i) {
		node[i] = 1;
		if((int)g[i].size()==1) {
			root = i;
			node[i] = 0;
		}
	}
	int spec = g[root][0];
	node[spec] = 0;
	for(int i: g[spec]) {
		if(i == root) continue;
		is_bit[i] = 1;
		node[i] = 0;
	}
	for(int i=0; i<U; ++i) {
		if(is_bit[C[i]] && is_bit[D[i]]) {
			gb[C[i]].push_back(D[i]);
			gb[D[i]].push_back(C[i]);
		}
	}
	for(int i=0; i<V; ++i) {
		if((int)gb[i].size()==1 && (int)g[i].size() >= N/2+2) {
			first_bit = i;
		}
	}
	for(int i=0; i<V; ++i) {
		if((int)gb[i].size()==MAXB/2) {
			bool ok = 1;
			for(int j: gb[i]) {
				if(j==first_bit) ok=0;
			}
			if(ok) mid_bit = i;
		}
	}
	for(int i: gb[mid_bit]) {
		sec_half[i] = 1;
	}
	for(int i=0; i<V; ++i) {
		if(!is_bit[i]) continue;
		int num = gb[i].size();
		if(!sec_half[i]) {
			bits[i] = num-1;
		}
		else {
			bits[i] = MAXB/2+num-1;
		}
	}
	
	for(int i=0; i<V; ++i) {
		if(!node[i]) continue;
		for(int j: g[i]) {
			if(is_bit[j]) {
				id[i] += (1<<bits[j]);
			}
		}
		id[i]--;
	}
	for(int i=0; i<U; ++i) {
		if(node[C[i]] && node[D[i]]) edges.push_back(mp(id[C[i]], id[D[i]]));
	}
	InitMap(V-(MAXB+2), edges.size());
	int NN = V - (MAXB+2);
	for(auto i: edges) {
		assert(i.st>=0 && i.st<NN && i.nd>=0 && i.nd<NN);
		MakeMap(i.st, i.nd);	
	}
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5044 KB Output is correct
2 Correct 5 ms 4960 KB Output is correct
3 Correct 6 ms 4832 KB Output is correct
4 Correct 5 ms 5060 KB Output is correct
5 Correct 6 ms 4960 KB Output is correct
6 Correct 6 ms 4832 KB Output is correct
7 Correct 5 ms 5044 KB Output is correct
8 Correct 5 ms 4960 KB Output is correct
9 Correct 6 ms 4960 KB Output is correct
10 Correct 6 ms 4832 KB Output is correct
11 Runtime error 9 ms 6112 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5044 KB Output is correct
2 Correct 5 ms 4960 KB Output is correct
3 Correct 6 ms 4832 KB Output is correct
4 Correct 5 ms 5060 KB Output is correct
5 Correct 6 ms 4960 KB Output is correct
6 Correct 6 ms 4832 KB Output is correct
7 Correct 5 ms 5044 KB Output is correct
8 Correct 5 ms 4960 KB Output is correct
9 Correct 6 ms 4960 KB Output is correct
10 Correct 6 ms 4832 KB Output is correct
11 Runtime error 9 ms 6112 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 29636 KB Output is correct : V - N = 12
2 Correct 540 ms 26200 KB Output is correct : V - N = 12
3 Correct 191 ms 14256 KB Output is correct : V - N = 12
4 Correct 14 ms 5484 KB Output is correct : V - N = 12
5 Correct 127 ms 10480 KB Output is correct : V - N = 12
6 Correct 510 ms 24048 KB Output is correct : V - N = 12
7 Correct 893 ms 29440 KB Output is correct : V - N = 12
8 Correct 653 ms 27728 KB Output is correct : V - N = 12
9 Correct 302 ms 16724 KB Output is correct : V - N = 12
10 Correct 48 ms 6644 KB Output is correct : V - N = 12
11 Correct 77 ms 7804 KB Output is correct : V - N = 12
12 Correct 434 ms 18504 KB Output is correct : V - N = 12
13 Correct 766 ms 28564 KB Output is correct : V - N = 12
14 Correct 717 ms 29152 KB Output is correct : V - N = 12
15 Correct 404 ms 22972 KB Output is correct : V - N = 12
16 Correct 123 ms 8896 KB Output is correct : V - N = 12
17 Correct 19 ms 5980 KB Output is correct : V - N = 12
18 Correct 295 ms 15636 KB Output is correct : V - N = 12
19 Correct 745 ms 27164 KB Output is correct : V - N = 12
20 Correct 712 ms 29668 KB Output is correct : V - N = 12
21 Correct 256 ms 12484 KB Output is correct : V - N = 12
22 Runtime error 193 ms 14804 KB Execution killed with signal 6 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -