oj.uz

Submission #56699

# Submission time Handle Problem Language Result Execution time Memory
56699 2018-07-12T08:12:44 Z 노영훈(#1616) Airline Route Map (JOI18_airline) C++11
37 / 100
 687 ms 30824 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

// const int MX=1010;

int n_A, m_A;

vector<pii> E;

void Alice( int N, int M, int A[], int B[] ){
	n_A=N, m_A=M;
	for(int i=0; i<m_A; i++){
		E.push_back({A[i], B[i]});
	}

	int P=N, Q=N+1, R=N+11;

	int X[10];
	for(int i=0; i<10; i++) X[i]=N+i+2;

	for(int i=0; i<N; i++){
		for(int j=0; j<10; j++)
			if(i&(1<<j))
				E.push_back({i, X[j]});
	}

	for(int i=0; i<9; i++)
		E.push_back({X[i], P});
	
	for(int i=0; i<N; i++)
		E.push_back({i, P});
	
	for(int i=0; i<9; i++)
		E.push_back({X[i], Q});

	for(int i=4; i<8; i++)
		E.push_back({X[i], R});

	for(int i=0; i<3; i++)
		E.push_back({X[i], X[3]}), E.push_back({X[i+4], X[7]});

	E.push_back({X[3], X[7]});

	E.push_back({X[1], X[2]}), E.push_back({X[5], X[6]});

	E.push_back({X[2], X[6]});

	InitG(N+12, E.size());

	for(int i=0; i<(int)E.size(); i++){
		MakeG(i, E[i].first, E[i].second);
		// cout<<E[i].first<<' '<<E[i].second<<'\n';
	}

}


#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MX=2020;

int n_B, m_B;

bool G[MX][MX];
int deg1[MX];
vector<pii> ans;

void Bob( int V, int U, int C[], int D[] ){
	n_B=V, m_B=U;
	for(int i=0; i<m_B; i++){
		G[C[i]][D[i]]=G[D[i]][C[i]]=true;
		deg1[C[i]]++, deg1[D[i]]++;
	}

	int P, Q, R, N=V-12;

	for(int i=0; i<V; i++)
		if(deg1[i]==N+9) P=i;
	
	for(int i=0; i<V; i++){
		if(i==P) continue;
		if(!G[i][P]){
			if(deg1[i]==9) Q=i;
			else R=i;
		}
	}

	int X[10], bck=0;
	int deg2[10]={};
	bool hi[10]={};
	X[9]=R;

	for(int i=0; i<V; i++){
		if(G[i][Q]) X[bck++]=i;
	}

	for(int i=0; i<9; i++)
		for(int j=i+1; j<9; j++)
			if(G[X[i]][X[j]]) deg2[i]++, deg2[j]++;
	
	for(int i=0; i<9; i++)
		if(deg2[i]==0){
			swap(deg2[i], deg2[8]), swap(X[i], X[8]);
			break;
		}

	for(int i=0; i<8; i++)
		if(G[X[i]][R]) hi[i]=true;
	

	// for(int i=0; i<8; i++)
	// 	cout<<X[i]<<' ';
	// cout<<'\n';
	// for(int i=0; i<8; i++)
	// 	cout<<deg2[i]<<' ';
	// cout<<'\n';
	// cout<<"SORTING...\n";

	pii T[10];
	for(int i=0; i<8; i++) T[i]={deg2[i]+5*hi[i], X[i]};
	sort(T, T+8);
	for(int i=0; i<8; i++)
		X[i]=T[i].second;

	// for(int i=0; i<10; i++)
	// 	cout<<X[i]<<' ';
	// cout<<'\n';

	int rev[MX]={};
	bool out[MX]={};

	for(int i=0; i<10; i++) out[X[i]]=true;
	out[P]=out[Q]=out[R]=true;

	for(int i=0; i<V; i++){
		if(out[i]) continue;
		for(int j=0; j<10; j++)
			rev[i]+=(G[i][X[j]] ? (1<<j) : 0);
	}

	int cnt=0;

	for(int i=0; i<V; i++){
		for(int j=i+1; j<V; j++){
			if(out[i] || out[j]) continue;
			if(!G[i][j]) continue;
			cnt++;
			// int x=rev[i], y=rev[j];
			// 	cout<<x<<' '<<y<<'\n';
			// int x=rev[i], y=rev[j];
			// ans.push_back({x,y});
		}
	}

	// cout<<P<<' '<<Q<<' '<<R<<'\n';

	// for(int i=0; i<V; i++)
	// 	cout<<rev[i]<<' ';
	// cout<<'\n';

	InitMap(N, cnt);
	
	for(int i=0; i<V; i++){
		for(int j=i+1; j<V; j++){
			if(out[i] || out[j]) continue;
			if(!G[i][j]) continue;
			int x=rev[i], y=rev[j];
			MakeMap(x,y);
		}
	}

	/*


	// cout<<P<<' '<<Q<<' '<<R<<'\n';
	// cout<<deg1[P]<<' '<<deg1[Q]<<' '<<deg1[R]<<'\n';

	InitMap(N, ans.size());

	for(pii &p:ans)
		MakeMap(p.first, p.second);
	*/
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:40:6: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  X[9]=R;
  ~~~~^~
Bob.cpp:82:8: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
  out[P]=out[Q]=out[R]=true;
  ~~~~~~^~~~~~~~~~~~~~~~~~~
Bob.cpp:82:15: warning: 'Q' may be used uninitialized in this function [-Wmaybe-uninitialized]
  out[P]=out[Q]=out[R]=true;
         ~~~~~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6640 KB Output is correct
2 Correct 8 ms 6640 KB Output is correct
3 Correct 8 ms 6992 KB Output is correct
4 Correct 8 ms 6768 KB Output is correct
5 Correct 6 ms 6640 KB Output is correct
6 Correct 13 ms 6640 KB Output is correct
7 Correct 7 ms 6896 KB Output is correct
8 Correct 7 ms 6976 KB Output is correct
9 Correct 6 ms 6640 KB Output is correct
10 Correct 6 ms 6728 KB Output is correct
11 Correct 7 ms 6736 KB Output is correct
12 Correct 7 ms 6736 KB Output is correct
13 Correct 7 ms 6640 KB Output is correct
14 Correct 6 ms 6896 KB Output is correct
15 Correct 6 ms 6640 KB Output is correct
16 Correct 6 ms 6896 KB Output is correct
17 Correct 6 ms 6640 KB Output is correct
18 Correct 6 ms 6640 KB Output is correct
19 Correct 6 ms 6680 KB Output is correct
20 Correct 6 ms 6640 KB Output is correct
21 Correct 6 ms 6640 KB Output is correct
22 Correct 7 ms 6928 KB Output is correct
23 Correct 7 ms 6640 KB Output is correct
24 Correct 6 ms 6896 KB Output is correct
25 Correct 6 ms 6896 KB Output is correct
26 Correct 7 ms 6896 KB Output is correct
27 Correct 6 ms 6696 KB Output is correct
28 Correct 8 ms 6640 KB Output is correct
29 Correct 8 ms 6896 KB Output is correct
30 Correct 8 ms 6640 KB Output is correct
31 Correct 6 ms 6896 KB Output is correct
32 Correct 7 ms 6696 KB Output is correct
33 Correct 8 ms 6896 KB Output is correct
34 Correct 7 ms 6648 KB Output is correct
35 Correct 8 ms 6896 KB Output is correct
36 Correct 7 ms 6640 KB Output is correct
37 Correct 13 ms 6640 KB Output is correct
38 Correct 7 ms 6640 KB Output is correct
39 Correct 6 ms 6896 KB Output is correct
40 Correct 6 ms 6896 KB Output is correct
41 Correct 8 ms 6896 KB Output is correct
42 Correct 7 ms 6640 KB Output is correct
43 Correct 6 ms 6736 KB Output is correct
44 Correct 6 ms 6640 KB Output is correct
45 Correct 7 ms 6896 KB Output is correct
46 Correct 10 ms 6640 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 6 ms 6640 KB Output is correct
49 Correct 7 ms 6640 KB Output is correct
50 Correct 6 ms 6624 KB Output is correct
51 Correct 7 ms 6728 KB Output is correct
52 Correct 10 ms 6896 KB Output is correct
53 Correct 8 ms 6896 KB Output is correct
54 Correct 7 ms 6640 KB Output is correct
55 Correct 7 ms 6896 KB Output is correct
56 Correct 7 ms 6640 KB Output is correct
57 Correct 6 ms 6896 KB Output is correct
58 Correct 7 ms 6904 KB Output is correct
59 Correct 8 ms 6896 KB Output is correct
60 Correct 8 ms 6640 KB Output is correct
61 Correct 8 ms 6640 KB Output is correct
62 Correct 7 ms 6896 KB Output is correct
63 Correct 6 ms 6640 KB Output is correct
64 Correct 7 ms 6736 KB Output is correct
65 Correct 8 ms 6640 KB Output is correct
66 Correct 8 ms 6896 KB Output is correct
67 Correct 8 ms 6640 KB Output is correct
68 Correct 8 ms 6816 KB Output is correct
69 Correct 8 ms 6640 KB Output is correct
70 Correct 8 ms 6640 KB Output is correct
71 Correct 7 ms 6712 KB Output is correct
72 Correct 8 ms 6640 KB Output is correct
73 Correct 8 ms 6640 KB Output is correct
74 Correct 7 ms 6896 KB Output is correct
75 Correct 7 ms 6896 KB Output is correct
76 Correct 8 ms 6736 KB Output is correct
77 Correct 8 ms 6896 KB Output is correct
78 Correct 8 ms 6640 KB Output is correct
79 Correct 8 ms 6648 KB Output is correct
80 Correct 8 ms 6896 KB Output is correct
81 Correct 8 ms 6640 KB Output is correct
82 Correct 8 ms 6640 KB Output is correct
83 Correct 7 ms 6896 KB Output is correct
84 Correct 7 ms 6640 KB Output is correct
85 Correct 8 ms 6736 KB Output is correct
86 Correct 8 ms 6640 KB Output is correct
87 Correct 8 ms 6904 KB Output is correct
88 Correct 8 ms 6640 KB Output is correct
89 Correct 8 ms 6896 KB Output is correct
90 Correct 8 ms 6648 KB Output is correct
91 Correct 7 ms 6640 KB Output is correct
92 Correct 7 ms 6640 KB Output is correct
93 Correct 8 ms 6896 KB Output is correct
94 Correct 8 ms 6896 KB Output is correct
95 Correct 8 ms 6640 KB Output is correct
96 Correct 8 ms 6640 KB Output is correct
97 Correct 8 ms 6904 KB Output is correct
98 Correct 8 ms 6640 KB Output is correct
99 Correct 8 ms 6896 KB Output is correct
100 Correct 8 ms 6736 KB Output is correct
101 Correct 8 ms 6632 KB Output is correct
102 Correct 8 ms 6640 KB Output is correct
103 Correct 8 ms 6640 KB Output is correct
104 Correct 8 ms 6640 KB Output is correct
105 Correct 8 ms 6696 KB Output is correct
106 Correct 8 ms 6648 KB Output is correct
107 Correct 8 ms 6648 KB Output is correct
108 Correct 7 ms 6896 KB Output is correct
109 Correct 8 ms 6648 KB Output is correct
110 Correct 8 ms 6896 KB Output is correct
111 Correct 6 ms 6648 KB Output is correct
112 Correct 7 ms 6640 KB Output is correct
113 Correct 6 ms 6896 KB Output is correct
114 Correct 8 ms 6896 KB Output is correct
115 Correct 7 ms 6712 KB Output is correct
116 Correct 6 ms 6640 KB Output is correct
117 Correct 8 ms 6744 KB Output is correct
118 Correct 8 ms 6640 KB Output is correct

Subtask #3
0 / 63.0

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