Submission #56724

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56724	2018-07-12T08:50:18 Z	노영훈(#1616)	Airline Route Map (JOI18_airline)	C++11	37 / 100	714 ms	30944 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	6648 KB	Output is correct
2	Correct	8 ms	6896 KB	Output is correct
3	Correct	7 ms	6896 KB	Output is correct
4	Correct	12 ms	6640 KB	Output is correct
5	Correct	7 ms	6736 KB	Output is correct
6	Correct	7 ms	6640 KB	Output is correct
7	Correct	7 ms	6896 KB	Output is correct
8	Correct	7 ms	6896 KB	Output is correct
9	Correct	6 ms	6680 KB	Output is correct
10	Correct	6 ms	6896 KB	Output is correct
11	Correct	17 ms	6736 KB	Output is correct
12	Correct	6 ms	6640 KB	Output is correct
13	Correct	8 ms	6736 KB	Output is correct
14	Correct	8 ms	6640 KB	Output is correct
15	Correct	8 ms	6896 KB	Output is correct
16	Correct	7 ms	6880 KB	Output is correct
17	Correct	6 ms	6928 KB	Output is correct
18	Correct	7 ms	6736 KB	Output is correct
19	Correct	8 ms	6728 KB	Output is correct
20	Correct	8 ms	6648 KB	Output is correct
21	Correct	8 ms	6736 KB	Output is correct
22	Correct	8 ms	6640 KB	Output is correct
23	Correct	8 ms	6568 KB	Output is correct
24	Correct	8 ms	6640 KB	Output is correct
25	Correct	8 ms	6728 KB	Output is correct
26	Correct	8 ms	6640 KB	Output is correct
27	Correct	7 ms	6640 KB	Output is correct
28	Correct	8 ms	6784 KB	Output is correct
29	Correct	8 ms	6640 KB	Output is correct
30	Correct	7 ms	6680 KB	Output is correct
31	Correct	8 ms	6640 KB	Output is correct
32	Correct	7 ms	6640 KB	Output is correct
33	Correct	8 ms	6552 KB	Output is correct
34	Correct	8 ms	6896 KB	Output is correct
35	Correct	8 ms	6896 KB	Output is correct
36	Correct	8 ms	6896 KB	Output is correct
37	Correct	7 ms	6640 KB	Output is correct
38	Correct	8 ms	6896 KB	Output is correct
39	Correct	8 ms	6896 KB	Output is correct
40	Correct	8 ms	6640 KB	Output is correct
41	Correct	8 ms	6896 KB	Output is correct
42	Correct	8 ms	6896 KB	Output is correct
43	Correct	7 ms	6640 KB	Output is correct
44	Correct	8 ms	6896 KB	Output is correct
45	Correct	8 ms	6640 KB	Output is correct
46	Correct	6 ms	6984 KB	Output is correct
47	Correct	8 ms	6776 KB	Output is correct
48	Correct	8 ms	6736 KB	Output is correct
49	Correct	8 ms	6640 KB	Output is correct
50	Correct	7 ms	6736 KB	Output is correct
51	Correct	8 ms	6640 KB	Output is correct
52	Correct	8 ms	6640 KB	Output is correct
53	Correct	8 ms	6640 KB	Output is correct
54	Correct	8 ms	6640 KB	Output is correct
55	Correct	8 ms	6736 KB	Output is correct
56	Correct	7 ms	6736 KB	Output is correct
57	Correct	7 ms	6640 KB	Output is correct
58	Correct	8 ms	6896 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6648 KB	Output is correct
2	Correct	8 ms	6896 KB	Output is correct
3	Correct	7 ms	6896 KB	Output is correct
4	Correct	12 ms	6640 KB	Output is correct
5	Correct	7 ms	6736 KB	Output is correct
6	Correct	7 ms	6640 KB	Output is correct
7	Correct	7 ms	6896 KB	Output is correct
8	Correct	7 ms	6896 KB	Output is correct
9	Correct	6 ms	6680 KB	Output is correct
10	Correct	6 ms	6896 KB	Output is correct
11	Correct	17 ms	6736 KB	Output is correct
12	Correct	6 ms	6640 KB	Output is correct
13	Correct	8 ms	6736 KB	Output is correct
14	Correct	8 ms	6640 KB	Output is correct
15	Correct	8 ms	6896 KB	Output is correct
16	Correct	7 ms	6880 KB	Output is correct
17	Correct	6 ms	6928 KB	Output is correct
18	Correct	7 ms	6736 KB	Output is correct
19	Correct	8 ms	6728 KB	Output is correct
20	Correct	8 ms	6648 KB	Output is correct
21	Correct	8 ms	6736 KB	Output is correct
22	Correct	8 ms	6640 KB	Output is correct
23	Correct	8 ms	6568 KB	Output is correct
24	Correct	8 ms	6640 KB	Output is correct
25	Correct	8 ms	6728 KB	Output is correct
26	Correct	8 ms	6640 KB	Output is correct
27	Correct	7 ms	6640 KB	Output is correct
28	Correct	8 ms	6784 KB	Output is correct
29	Correct	8 ms	6640 KB	Output is correct
30	Correct	7 ms	6680 KB	Output is correct
31	Correct	8 ms	6640 KB	Output is correct
32	Correct	7 ms	6640 KB	Output is correct
33	Correct	8 ms	6552 KB	Output is correct
34	Correct	8 ms	6896 KB	Output is correct
35	Correct	8 ms	6896 KB	Output is correct
36	Correct	8 ms	6896 KB	Output is correct
37	Correct	7 ms	6640 KB	Output is correct
38	Correct	8 ms	6896 KB	Output is correct
39	Correct	8 ms	6896 KB	Output is correct
40	Correct	8 ms	6640 KB	Output is correct
41	Correct	8 ms	6896 KB	Output is correct
42	Correct	8 ms	6896 KB	Output is correct
43	Correct	7 ms	6640 KB	Output is correct
44	Correct	8 ms	6896 KB	Output is correct
45	Correct	8 ms	6640 KB	Output is correct
46	Correct	6 ms	6984 KB	Output is correct
47	Correct	8 ms	6776 KB	Output is correct
48	Correct	8 ms	6736 KB	Output is correct
49	Correct	8 ms	6640 KB	Output is correct
50	Correct	7 ms	6736 KB	Output is correct
51	Correct	8 ms	6640 KB	Output is correct
52	Correct	8 ms	6640 KB	Output is correct
53	Correct	8 ms	6640 KB	Output is correct
54	Correct	8 ms	6640 KB	Output is correct
55	Correct	8 ms	6736 KB	Output is correct
56	Correct	7 ms	6736 KB	Output is correct
57	Correct	7 ms	6640 KB	Output is correct
58	Correct	8 ms	6896 KB	Output is correct
59	Correct	8 ms	6896 KB	Output is correct
60	Correct	6 ms	6776 KB	Output is correct
61	Correct	8 ms	6896 KB	Output is correct
62	Correct	8 ms	6640 KB	Output is correct
63	Correct	8 ms	6896 KB	Output is correct
64	Correct	8 ms	6640 KB	Output is correct
65	Correct	8 ms	6640 KB	Output is correct
66	Correct	8 ms	6640 KB	Output is correct
67	Correct	8 ms	6640 KB	Output is correct
68	Correct	8 ms	6640 KB	Output is correct
69	Correct	8 ms	6664 KB	Output is correct
70	Correct	8 ms	6640 KB	Output is correct
71	Correct	8 ms	6640 KB	Output is correct
72	Correct	7 ms	6840 KB	Output is correct
73	Correct	7 ms	6640 KB	Output is correct
74	Correct	7 ms	6712 KB	Output is correct
75	Correct	7 ms	6640 KB	Output is correct
76	Correct	7 ms	6832 KB	Output is correct
77	Correct	8 ms	6640 KB	Output is correct
78	Correct	8 ms	6640 KB	Output is correct
79	Correct	19 ms	6640 KB	Output is correct
80	Correct	8 ms	6648 KB	Output is correct
81	Correct	7 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	7 ms	6640 KB	Output is correct
85	Correct	7 ms	6744 KB	Output is correct
86	Correct	8 ms	6760 KB	Output is correct
87	Correct	6 ms	6640 KB	Output is correct
88	Correct	7 ms	6896 KB	Output is correct
89	Correct	18 ms	6640 KB	Output is correct
90	Correct	7 ms	6640 KB	Output is correct
91	Correct	7 ms	6896 KB	Output is correct
92	Correct	9 ms	6736 KB	Output is correct
93	Correct	7 ms	6648 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	6640 KB	Output is correct
98	Correct	8 ms	6640 KB	Output is correct
99	Correct	6 ms	6736 KB	Output is correct
100	Correct	8 ms	6896 KB	Output is correct
101	Correct	7 ms	6992 KB	Output is correct
102	Correct	6 ms	6776 KB	Output is correct
103	Correct	8 ms	6736 KB	Output is correct
104	Correct	8 ms	6640 KB	Output is correct
105	Correct	8 ms	6904 KB	Output is correct
106	Correct	8 ms	6896 KB	Output is correct
107	Correct	8 ms	6632 KB	Output is correct
108	Correct	8 ms	6736 KB	Output is correct
109	Correct	8 ms	6640 KB	Output is correct
110	Correct	8 ms	6648 KB	Output is correct
111	Correct	8 ms	6784 KB	Output is correct
112	Correct	8 ms	6640 KB	Output is correct
113	Correct	8 ms	6736 KB	Output is correct
114	Correct	8 ms	6896 KB	Output is correct
115	Correct	8 ms	6896 KB	Output is correct
116	Correct	8 ms	6672 KB	Output is correct
117	Correct	8 ms	6736 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	Correct	640 ms	30944 KB	Output is correct : V - N = 12
2	Correct	504 ms	25696 KB	Output is correct : V - N = 12
3	Correct	213 ms	14232 KB	Output is correct : V - N = 12
4	Correct	18 ms	7512 KB	Output is correct : V - N = 12
5	Correct	140 ms	11456 KB	Output is correct : V - N = 12
6	Correct	465 ms	22472 KB	Output is correct : V - N = 12
7	Correct	692 ms	30472 KB	Output is correct : V - N = 12
8	Correct	595 ms	27960 KB	Output is correct : V - N = 12
9	Correct	307 ms	17408 KB	Output is correct : V - N = 12
10	Correct	43 ms	8472 KB	Output is correct : V - N = 12
11	Correct	67 ms	9440 KB	Output is correct : V - N = 12
12	Correct	343 ms	19272 KB	Output is correct : V - N = 12
13	Correct	606 ms	29240 KB	Output is correct : V - N = 12
14	Correct	671 ms	29792 KB	Output is correct : V - N = 12
15	Correct	383 ms	20904 KB	Output is correct : V - N = 12
16	Correct	95 ms	10216 KB	Output is correct : V - N = 12
17	Correct	22 ms	7736 KB	Output is correct : V - N = 12
18	Correct	244 ms	15888 KB	Output is correct : V - N = 12
19	Correct	563 ms	26864 KB	Output is correct : V - N = 12
20	Correct	686 ms	30728 KB	Output is correct : V - N = 12
21	Correct	185 ms	13392 KB	Output is correct : V - N = 12
22	Correct	152 ms	12016 KB	Output is correct : V - N = 12
23	Correct	60 ms	9208 KB	Output is correct : V - N = 12
24	Correct	9 ms	6992 KB	Output is correct : V - N = 12
25	Correct	40 ms	8344 KB	Output is correct : V - N = 12
26	Correct	127 ms	11200 KB	Output is correct : V - N = 12
27	Correct	183 ms	13312 KB	Output is correct : V - N = 12
28	Correct	198 ms	12808 KB	Output is correct : V - N = 12
29	Correct	89 ms	9920 KB	Output is correct : V - N = 12
30	Correct	13 ms	7504 KB	Output is correct : V - N = 12
31	Correct	13 ms	7112 KB	Output is correct : V - N = 12
32	Correct	13 ms	6992 KB	Output is correct : V - N = 12
33	Correct	12 ms	7152 KB	Output is correct : V - N = 12
34	Correct	13 ms	6992 KB	Output is correct : V - N = 12
35	Correct	13 ms	7152 KB	Output is correct : V - N = 12
36	Incorrect	714 ms	30832 KB	Wrong Answer [11]
37	Halted	0 ms	0 KB	-

Submission #56724

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