oj.uz

Submission #336547

# Submission time Handle Problem Language Result Execution time Memory
336547 2020-12-15T15:29:56 Z amoo_safar Airline Route Map (JOI18_airline) C++17
0 / 100
 1456 ms 60964 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back

using namespace std;

const int Log = 10;

typedef pair<int, int> pii;

int bad[1 << Log];
vector<int> Good;

void FillBad(){
	memset(bad, 0, sizeof bad);
	bad[0] = 1;
	for(int i = 0; i < Log; i++)
		bad[1 << i] = 1;
	// for(int i = 0; i + 1 < Log; i++)
	// 	bad[3 << i] = 1;
	for(int i = 0; i < (1 << Log); i++)
		if(!bad[i])
			Good.pb(i);
}

vector<pii> E;
void Alice(int n, int m, int A[], int B[]){
	FillBad();
	E.clear();
	for(int i = 0; i < m; i++) E.pb({A[i], B[i]});
	///
	for(int i = n; i < n + 9; i++) E.pb({i, i + 1});
	for(int i = n; i <= n + 9; i++) E.pb({n + 10, i});
	E.pb({n + 11, n + 10}); E.pb({n + 11, n + 9});
	///
	assert((int) Good.size() >= n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < Log; j++){
			if(Good[i] >> j & 1)
				E.pb({n + j, i});
		}
	}

	m = E.size();
	InitG( n + 12, m);
	for(int i = 0; i < m; i++)
		MakeG(i, E[i].F, E[i].S);
	return ;
}


#include "Boblib.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back

using namespace std;

const int Log = 10;

typedef pair<int, int> pii;

const int N = 2e3;

int bad2[1 << Log];
vector<int> GD;

void FillBad2(){
	memset(bad2, 0, sizeof bad2);
	bad2[0] = 1;
	for(int i = 0; i < Log; i++)
		bad2[1 << i] = 1;
	// for(int i = 0; i + 1 < Log; i++)
	// 	bad2[3 << i] = 1;
	for(int i = 0; i < (1 << Log); i++)
		if(!bad2[i])
			GD.pb(i);
}



vector<int> G[N];
map<pii, int> mp;
void AddEdge(int u, int v){
	mp[{min(u, v), max(u, v)}] = 1;
	G[u].pb(v);
	G[v].pb(u);
}
bool IsEdge(int u, int v){
	return mp.count({min(u, v), max(u, v)}) > 0;
}


int deg[N];
int mk[N];
int n, m;
int FindCommon(int u, int v){
	for(int i = 0; i < n; i++){
		if(!mk[i] && IsEdge(u, i) && IsEdge(v, i))
			return i;
	}
	return -1;
}

int cntCommon(int u, int v){
	int res = 0;
	for(int i = 0; i < n; i++){
		if(!mk[i] && IsEdge(u, i) && IsEdge(v, i))
			res ++;
	}
	return res;
}

int ord[N];

int val[N];

void Bob(int V, int U, int C[], int D[] ){
	n = V; m = U;
	FillBad2();

	for(int i = 0; i < U; i++){
		AddEdge(C[i], D[i]);
		deg[C[i]] ++;
		deg[D[i]] ++;
	}
	int idx = -1;
	for(int i = 0; i < V; i++)
		if(deg[i] == 2 && IsEdge(G[i][0], G[i][1])){
			assert(idx == -1);
			idx = i;
		}
	assert(idx != -1);
	vector<int> adj;
	for(int i = 0; i < m; i++){
		if(C[i] == idx)
			adj.pb(D[i]);
		if(D[i] == idx)
			adj.pb(C[i]);
	}
	assert(adj.size() == 2);

	mk[idx] = 1;
	int X = FindCommon(adj[0], adj[1]);
	mk[adj[0]] = mk[adj[1]] = 1;

	int Y = -1;
	if(deg[adj[0]] != 11){
		Y = adj[1];
	} else if(deg[adj[1]] != 11){
		Y = adj[0];
	} else {
		if(cntCommon(X, adj[0]) != 1)
			Y = adj[1];
		if(cntCommon(X, adj[1]) != 1)
			Y = adj[0];
	}
	assert(Y != -1);
	// int Y = (FindCommon(adj[0], X) == -1 ? adj[1] : adj[0]);

	memset(mk, 0, sizeof mk);
	mk[idx] = 1; mk[Y] = 1;
	int la = idx;
	for(int i = 0; i < 10; i++){
		int com = FindCommon(la, Y);

		assert(com != -1);
		ord[com] = 9 - i;
		mk[com] = 1;
		la = com;
	}
	for(int i = 0; i < n; i++){
		if(mk[i]) continue;
		int res = 0;
		// cerr << "# ";
		for(auto nei : G[i]){
			if(mk[nei]){
				res += (1 << ord[nei]);
				// cerr << ord[nei] << ' ';
			}
		}
		// cerr << '\n';
		val[i] = lower_bound(GD.begin(), GD.end(), res) - GD.begin();
		// cerr << "! " << n << " " << res << '\n';
	}
	vector<pii> E;
	for(int i = 0; i < m; i++){
		if(mk[C[i]] || mk[D[i]]) continue;
		E.pb({val[C[i]], val[D[i]]});
	}
	InitMap( n - 12, E.size());
	for(auto [u, v] : E)

		MakeMap(u, v);
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 60964 KB Output is correct : V - N = 12
2 Correct 1004 ms 50184 KB Output is correct : V - N = 12
3 Correct 329 ms 23668 KB Output is correct : V - N = 12
4 Correct 16 ms 6080 KB Output is correct : V - N = 12
5 Correct 192 ms 15992 KB Output is correct : V - N = 12
6 Correct 798 ms 44216 KB Output is correct : V - N = 12
7 Correct 1456 ms 60168 KB Output is correct : V - N = 12
8 Correct 1127 ms 55508 KB Output is correct : V - N = 12
9 Correct 511 ms 30268 KB Output is correct : V - N = 12
10 Correct 54 ms 8432 KB Output is correct : V - N = 12
11 Correct 110 ms 10548 KB Output is correct : V - N = 12
12 Correct 604 ms 34348 KB Output is correct : V - N = 12
13 Correct 1219 ms 57588 KB Output is correct : V - N = 12
14 Correct 1297 ms 58860 KB Output is correct : V - N = 12
15 Correct 727 ms 40732 KB Output is correct : V - N = 12
16 Correct 136 ms 12752 KB Output is correct : V - N = 12
17 Correct 28 ms 7008 KB Output is correct : V - N = 12
18 Correct 435 ms 27028 KB Output is correct : V - N = 12
19 Correct 1051 ms 53020 KB Output is correct : V - N = 12
20 Correct 1302 ms 60824 KB Output is correct : V - N = 12
21 Correct 274 ms 20988 KB Output is correct : V - N = 12
22 Correct 203 ms 17032 KB Output is correct : V - N = 12
23 Correct 82 ms 10216 KB Output is correct : V - N = 12
24 Runtime error 11 ms 6880 KB Execution killed with signal 6 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -