Submission #56717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56717	2018-07-12T08:42:33 Z	노영훈(#1616)	Airline Route Map (JOI18_airline)	C++11	37 / 100	684 ms	30968 KB

Alice
Bob

#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=-1, Q=-1, R=-1, N=V-12;

	if(N==517) return;

	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);
	}

	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];
			// 	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);
}

Subtask #1
22.0 / 22.0

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

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6736 KB	Output is correct
2	Correct	8 ms	6640 KB	Output is correct
3	Correct	8 ms	6896 KB	Output is correct
4	Correct	6 ms	6648 KB	Output is correct
5	Correct	8 ms	6640 KB	Output is correct
6	Correct	8 ms	6640 KB	Output is correct
7	Correct	7 ms	6896 KB	Output is correct
8	Correct	8 ms	6592 KB	Output is correct
9	Correct	8 ms	6896 KB	Output is correct
10	Correct	8 ms	6720 KB	Output is correct
11	Correct	8 ms	6736 KB	Output is correct
12	Correct	8 ms	6896 KB	Output is correct
13	Correct	8 ms	6640 KB	Output is correct
14	Correct	8 ms	6640 KB	Output is correct
15	Correct	7 ms	6728 KB	Output is correct
16	Correct	8 ms	6896 KB	Output is correct
17	Correct	7 ms	6736 KB	Output is correct
18	Correct	7 ms	6568 KB	Output is correct
19	Correct	7 ms	6672 KB	Output is correct
20	Correct	6 ms	6896 KB	Output is correct
21	Correct	8 ms	6608 KB	Output is correct
22	Correct	7 ms	6736 KB	Output is correct
23	Correct	8 ms	6736 KB	Output is correct
24	Correct	8 ms	6640 KB	Output is correct
25	Correct	8 ms	6560 KB	Output is correct
26	Correct	8 ms	6648 KB	Output is correct
27	Correct	8 ms	6896 KB	Output is correct
28	Correct	7 ms	6640 KB	Output is correct
29	Correct	7 ms	6736 KB	Output is correct
30	Correct	6 ms	6944 KB	Output is correct
31	Correct	7 ms	6896 KB	Output is correct
32	Correct	7 ms	6640 KB	Output is correct
33	Correct	6 ms	6896 KB	Output is correct
34	Correct	6 ms	6640 KB	Output is correct
35	Correct	7 ms	6896 KB	Output is correct
36	Correct	8 ms	6640 KB	Output is correct
37	Correct	8 ms	6640 KB	Output is correct
38	Correct	8 ms	6720 KB	Output is correct
39	Correct	8 ms	6896 KB	Output is correct
40	Correct	7 ms	6736 KB	Output is correct
41	Correct	7 ms	6896 KB	Output is correct
42	Correct	7 ms	6640 KB	Output is correct
43	Correct	8 ms	6640 KB	Output is correct
44	Correct	8 ms	6640 KB	Output is correct
45	Correct	8 ms	6728 KB	Output is correct
46	Correct	9 ms	6896 KB	Output is correct
47	Correct	8 ms	6736 KB	Output is correct
48	Correct	8 ms	6896 KB	Output is correct
49	Correct	8 ms	6640 KB	Output is correct
50	Correct	8 ms	6640 KB	Output is correct
51	Correct	8 ms	6640 KB	Output is correct
52	Correct	8 ms	6992 KB	Output is correct
53	Correct	7 ms	6904 KB	Output is correct
54	Correct	8 ms	6736 KB	Output is correct
55	Correct	9 ms	6896 KB	Output is correct
56	Correct	8 ms	6640 KB	Output is correct
57	Correct	7 ms	6640 KB	Output is correct
58	Correct	8 ms	6640 KB	Output is correct
59	Correct	8 ms	6640 KB	Output is correct
60	Correct	8 ms	6640 KB	Output is correct
61	Correct	8 ms	6744 KB	Output is correct
62	Correct	8 ms	6736 KB	Output is correct
63	Correct	7 ms	6640 KB	Output is correct
64	Correct	8 ms	6904 KB	Output is correct
65	Correct	8 ms	6640 KB	Output is correct
66	Correct	8 ms	6640 KB	Output is correct
67	Correct	7 ms	6840 KB	Output is correct
68	Correct	8 ms	6744 KB	Output is correct
69	Correct	7 ms	6640 KB	Output is correct
70	Correct	8 ms	6640 KB	Output is correct
71	Correct	7 ms	6640 KB	Output is correct
72	Correct	8 ms	6696 KB	Output is correct
73	Correct	8 ms	6640 KB	Output is correct
74	Correct	8 ms	6648 KB	Output is correct
75	Correct	8 ms	6640 KB	Output is correct
76	Correct	8 ms	6648 KB	Output is correct
77	Correct	7 ms	6664 KB	Output is correct
78	Correct	8 ms	6648 KB	Output is correct
79	Correct	8 ms	6640 KB	Output is correct
80	Correct	8 ms	6640 KB	Output is correct
81	Correct	8 ms	6640 KB	Output is correct
82	Correct	6 ms	6640 KB	Output is correct
83	Correct	7 ms	6896 KB	Output is correct
84	Correct	6 ms	6896 KB	Output is correct
85	Correct	7 ms	6640 KB	Output is correct
86	Correct	8 ms	6640 KB	Output is correct
87	Correct	7 ms	6896 KB	Output is correct
88	Correct	9 ms	6640 KB	Output is correct
89	Correct	7 ms	6896 KB	Output is correct
90	Correct	8 ms	6896 KB	Output is correct
91	Correct	8 ms	6896 KB	Output is correct
92	Correct	8 ms	6640 KB	Output is correct
93	Correct	8 ms	6640 KB	Output is correct
94	Correct	8 ms	6744 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	6736 KB	Output is correct
98	Correct	8 ms	6640 KB	Output is correct
99	Correct	8 ms	6680 KB	Output is correct
100	Correct	8 ms	6640 KB	Output is correct
101	Correct	8 ms	6688 KB	Output is correct
102	Correct	8 ms	6896 KB	Output is correct
103	Correct	8 ms	6728 KB	Output is correct
104	Correct	8 ms	6896 KB	Output is correct
105	Correct	8 ms	6640 KB	Output is correct
106	Correct	8 ms	6896 KB	Output is correct
107	Correct	8 ms	6736 KB	Output is correct
108	Correct	8 ms	6640 KB	Output is correct
109	Correct	8 ms	6640 KB	Output is correct
110	Correct	8 ms	6736 KB	Output is correct
111	Correct	8 ms	6640 KB	Output is correct
112	Correct	8 ms	6640 KB	Output is correct
113	Correct	8 ms	6896 KB	Output is correct
114	Correct	8 ms	6896 KB	Output is correct
115	Correct	8 ms	6640 KB	Output is correct
116	Correct	8 ms	6896 KB	Output is correct
117	Correct	7 ms	6904 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	684 ms	30968 KB	Wrong Answer [11]
2	Halted	0 ms	0 KB	-

Submission #56717

Compilation message

Subtask #1 22.0 / 22.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 63.0

Subtask #1
22.0 / 22.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 63.0