oj.uz

Submission #164065

# Submission time Handle Problem Language Result Execution time Memory
164065 2019-11-17T08:46:30 Z oolimry Airline Route Map (JOI18_airline) C++14
22 / 100
 952 ms 30656 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

void Alice( int n, int m, int A[], int B[] ){
	int cnt = 0;
	vector<int> nums;
	for(int i = 0;i < 1024;i++){
		int bits = 0;
		for(int j = 1;j < 1024;j *= 2){
			if((i & j) != 0) bits++;
		}
		if(bits >= 2){
			nums.push_back(i);
		}
		if(nums.size() == n) break;
	}
	typedef pair<int,int> ii;
	vector<ii> edges;
	for(int i = 0;i < m;i++){
		edges.push_back(ii(A[i],B[i]));
	}
	
	int x = n+10;
	int y = n+11;
	int anchor[10];
	for(int i = 0;i < 10;i++) anchor[i] = n+i;
	
	edges.push_back(ii(x,y));
	for(int i = 0;i < 10;i++){
		edges.push_back(ii(y,anchor[i]));
	}
	
	for(int i = 1;i < 9;i++){
		edges.push_back(ii(anchor[0],anchor[i]));
		edges.push_back(ii(anchor[i],anchor[i+1]));
	}
	
	
	for(int i = 0;i < n;i++){
		int k = nums[i];
		for(int j = 0;j < 10;j++){
			if((k & (1 << j)) != 0){
				edges.push_back(ii(i,anchor[j]));
			}
		}
	}
	/*
	for(ii x : edges){
		cout << x.first << " " << x.second << "\n";
	}
	//*/
	InitG(n+12,edges.size());
	for(int i = 0;i < edges.size();i++){
		MakeG(i,edges[i].first,edges[i].second);
	}
	//cout << "\n\n";
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

void Bob( int n, int m, int C[], int D[] ){
	if(n > 40) return;
	int on = n - 12;
	vector<int> nums;
	typedef pair<int,int> ii;

	bool adjMat[n][n];
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			adjMat[i][j] = false;
	for(int i = 0;i < 1024;i++){
		int bits = 0;
		for(int j = 1;j < 1024;j *= 2){
			if((i & j) != 0) bits++;
		}
		if(bits >= 2){
			nums.push_back(i);
		}
		if(nums.size() == on) break;
	}
	
	vector<int> adj[n];
	for(int i = 0;i < m;i++){
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
		//cout << C[i] << " " << D[i] << "\n";
		//edges.insert(ii(C[i],D[i]));
		//edges.insert(ii(D[i],C[i]));
		adjMat[C[i]][D[i]] = true;
		adjMat[D[i]][C[i]] = true;
	}
	int x, y;
	for(int i = 0;i < n;i++){
		if(adj[i].size() == 1){
			x = i;
			y = adj[i][0];
			break;
		}
	}
	
	//cout << x << "\n" << y << "\n";
	
	vector<int> aa;
	for(int i = 0;i < n;i++){
		if(i == x || i == y){
			continue;
		}
		if(adjMat[i][y]){
			aa.push_back(i);
		}
	}
	set<int> anchorSet;
	for(int k : aa){
		//cout << k << " ";
		anchorSet.insert(k);
	}
	
	int anchor[10];
	
	fill(anchor,anchor+10,-1);
	for(int i = 0;i < 10;i++){
		int cnt = 0;
		for(int j = 0;j < 10;j++){
			if(adjMat[aa[i]][aa[j]]){
				cnt++;
			}
		}
		if(cnt == 8){
			anchor[0] = aa[i];
		}
		else if(cnt == 1){
			anchor[9] = aa[i];
		}
	}
	
	int cur = anchor[9];
	for(int i = 9;i >= 2;i--){
		for(int v : adj[cur]){
			if(v != anchor[0] && anchorSet.find(v) != anchorSet.end()){
				if(i == 9 || v != anchor[i+1]){
					cur = v;
					anchor[i-1] = cur;
					break;
				} 
			}
		}
	}
	bool extras[n];
	int anchorMap[n];
	int normalMap[n];
	fill(extras,extras+n,false);
	//unordered_map<int,int> anchorMap;
	//cout << "\n";
	for(int i =0 ;i < 10;i++){
		//cout << anchor[i] << " ";
		extras[anchor[i]] = true;
		anchorMap[anchor[i]] = i;
	}
	extras[x] = true;
	extras[y] = true;
	//cout << "\n";
	//unordered_map<int,int> normalMap;
	for(int u = 0;u < n;u++){
		int value = 0;
		if(extras[u]) continue;
		for(int v : adj[u]){
			if(!extras[v]) continue;
			
			int bit = anchorMap[v];
			value |= (1 << bit);
		}
		int pos = lower_bound(nums.begin(),nums.end(),value) - nums.begin();
		normalMap[u] = pos;
		//cout << u << " " << pos << "\n";
	}
	vector<ii> finalEdges;
	for(int i = 0;i < m;i++){
		int u = C[i];
		int v = D[i];
		if(extras[u] || extras[v]) continue;
		finalEdges.push_back(ii(normalMap[u],normalMap[v]));
	}
	
	//cout << "\n";
	//for(ii k : finalEdges) cout << k.first << " " << k.second << "\n";
	
	InitMap(on, finalEdges.size());
	for(ii k : finalEdges) MakeMap(k.first,k.second);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(nums.size() == n) break;
      ~~~~~~~~~~~~^~~~
Alice.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < edges.size();i++){
                ~~^~~~~~~~~~~~~~
Alice.cpp:6:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(nums.size() == on) break;
      ~~~~~~~~~~~~^~~~~
Bob.cpp:103:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  extras[x] = true;
  ~~~~~~~~~~^~~~~~
Bob.cpp:104:12: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  extras[y] = true;
  ~~~~~~~~~~^~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6640 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 12 ms 6896 KB Output is correct
4 Correct 10 ms 6640 KB Output is correct
5 Correct 9 ms 6904 KB Output is correct
6 Correct 9 ms 6640 KB Output is correct
7 Correct 9 ms 6648 KB Output is correct
8 Correct 9 ms 6640 KB Output is correct
9 Correct 10 ms 6896 KB Output is correct
10 Correct 9 ms 6896 KB Output is correct
11 Correct 9 ms 6896 KB Output is correct
12 Correct 9 ms 6640 KB Output is correct
13 Correct 8 ms 6896 KB Output is correct
14 Correct 9 ms 6896 KB Output is correct
15 Correct 11 ms 6896 KB Output is correct
16 Correct 9 ms 6896 KB Output is correct
17 Correct 9 ms 6640 KB Output is correct
18 Correct 9 ms 6640 KB Output is correct
19 Correct 9 ms 6640 KB Output is correct
20 Correct 9 ms 6640 KB Output is correct
21 Correct 9 ms 6640 KB Output is correct
22 Correct 9 ms 6640 KB Output is correct
23 Correct 9 ms 6648 KB Output is correct
24 Correct 9 ms 6896 KB Output is correct
25 Correct 9 ms 6640 KB Output is correct
26 Correct 9 ms 6896 KB Output is correct
27 Correct 9 ms 6640 KB Output is correct
28 Correct 9 ms 6896 KB Output is correct
29 Correct 9 ms 6640 KB Output is correct
30 Correct 9 ms 6896 KB Output is correct
31 Correct 9 ms 6896 KB Output is correct
32 Correct 9 ms 6896 KB Output is correct
33 Correct 9 ms 6896 KB Output is correct
34 Correct 9 ms 6896 KB Output is correct
35 Correct 9 ms 6640 KB Output is correct
36 Correct 9 ms 6896 KB Output is correct
37 Correct 9 ms 6896 KB Output is correct
38 Correct 9 ms 6640 KB Output is correct
39 Correct 7 ms 6896 KB Output is correct
40 Correct 9 ms 6896 KB Output is correct
41 Correct 9 ms 6896 KB Output is correct
42 Correct 8 ms 6648 KB Output is correct
43 Correct 9 ms 6640 KB Output is correct
44 Correct 9 ms 6640 KB Output is correct
45 Correct 9 ms 6640 KB Output is correct
46 Correct 9 ms 6648 KB Output is correct
47 Correct 9 ms 6640 KB Output is correct
48 Correct 9 ms 6640 KB Output is correct
49 Correct 9 ms 6640 KB Output is correct
50 Correct 9 ms 6640 KB Output is correct
51 Correct 9 ms 6896 KB Output is correct
52 Correct 9 ms 6640 KB Output is correct
53 Correct 9 ms 6640 KB Output is correct
54 Correct 9 ms 6896 KB Output is correct
55 Correct 9 ms 6640 KB Output is correct
56 Correct 9 ms 6640 KB Output is correct
57 Correct 9 ms 6632 KB Output is correct
58 Correct 9 ms 6648 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6640 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 12 ms 6896 KB Output is correct
4 Correct 10 ms 6640 KB Output is correct
5 Correct 9 ms 6904 KB Output is correct
6 Correct 9 ms 6640 KB Output is correct
7 Correct 9 ms 6648 KB Output is correct
8 Correct 9 ms 6640 KB Output is correct
9 Correct 10 ms 6896 KB Output is correct
10 Correct 9 ms 6896 KB Output is correct
11 Correct 9 ms 6896 KB Output is correct
12 Correct 9 ms 6640 KB Output is correct
13 Correct 8 ms 6896 KB Output is correct
14 Correct 9 ms 6896 KB Output is correct
15 Correct 11 ms 6896 KB Output is correct
16 Correct 9 ms 6896 KB Output is correct
17 Correct 9 ms 6640 KB Output is correct
18 Correct 9 ms 6640 KB Output is correct
19 Correct 9 ms 6640 KB Output is correct
20 Correct 9 ms 6640 KB Output is correct
21 Correct 9 ms 6640 KB Output is correct
22 Correct 9 ms 6640 KB Output is correct
23 Correct 9 ms 6648 KB Output is correct
24 Correct 9 ms 6896 KB Output is correct
25 Correct 9 ms 6640 KB Output is correct
26 Correct 9 ms 6896 KB Output is correct
27 Correct 9 ms 6640 KB Output is correct
28 Correct 9 ms 6896 KB Output is correct
29 Correct 9 ms 6640 KB Output is correct
30 Correct 9 ms 6896 KB Output is correct
31 Correct 9 ms 6896 KB Output is correct
32 Correct 9 ms 6896 KB Output is correct
33 Correct 9 ms 6896 KB Output is correct
34 Correct 9 ms 6896 KB Output is correct
35 Correct 9 ms 6640 KB Output is correct
36 Correct 9 ms 6896 KB Output is correct
37 Correct 9 ms 6896 KB Output is correct
38 Correct 9 ms 6640 KB Output is correct
39 Correct 7 ms 6896 KB Output is correct
40 Correct 9 ms 6896 KB Output is correct
41 Correct 9 ms 6896 KB Output is correct
42 Correct 8 ms 6648 KB Output is correct
43 Correct 9 ms 6640 KB Output is correct
44 Correct 9 ms 6640 KB Output is correct
45 Correct 9 ms 6640 KB Output is correct
46 Correct 9 ms 6648 KB Output is correct
47 Correct 9 ms 6640 KB Output is correct
48 Correct 9 ms 6640 KB Output is correct
49 Correct 9 ms 6640 KB Output is correct
50 Correct 9 ms 6640 KB Output is correct
51 Correct 9 ms 6896 KB Output is correct
52 Correct 9 ms 6640 KB Output is correct
53 Correct 9 ms 6640 KB Output is correct
54 Correct 9 ms 6896 KB Output is correct
55 Correct 9 ms 6640 KB Output is correct
56 Correct 9 ms 6640 KB Output is correct
57 Correct 9 ms 6632 KB Output is correct
58 Correct 9 ms 6648 KB Output is correct
59 Incorrect 9 ms 6896 KB Wrong Answer [17]
60 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 952 ms 30656 KB Wrong Answer [17]
2 Halted 0 ms 0 KB -