Submission #313388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
313388	2020-10-15T23:35:57 Z	arthur_nascimento	Airline Route Map (JOI18_airline)	C++14	22 / 100	700 ms	30648 KB

Alice
Bob

#include "Alicelib.h"

#include <cassert>

#include <cstdio>

#include <bits/stdc++.h>

#define maxn 110

#define maxK 4100

#define ll long long

#define pb push_back

#define pii pair<int,int>

#define mod 1000000007 

#define debug(args...) //fprintf(stderr,args)

using namespace std;


void Alice( int N, int M, int A[], int B[] ){


	vector<pii> v;

	for(int i=0;i<M;i++)
		v.pb({A[i],B[i]});

	for(int i=0;i<11;i++)
		for(int j=0;j<N;j++)
			if(j & (1<<i))
				v.pb({i+N,j});

	for(int i=0;i<N+11;i++){
		if(i < N){
			v.pb({11+N,i});
			v.pb({12+N,i});
		}
		else if (i == N);
		else if(i < N + 6)
			v.pb({11+N,i});
		else
			v.pb({12+N,i});
	}

	for(int i=0;i<10;i++)
		v.pb({i+N,i+N+1});


	InitG(N+13,v.size());

	int bla = 0;
	
	for(pii i : v)
		MakeG(bla++, i.first,i.second);
	

}

#include "Boblib.h"

#include <cassert>

#include <cstdio>

#define maxn 1111

#include <bits/stdc++.h>



#define maxK 4100

#define ll long long

#define pb push_back

#define pii pair<int,int>

#define mod 1000000007 

#define debug(args...) //fprintf(stderr,args)

using namespace std;

int mrk[maxn];

int dg[maxn];

vector<int> L[maxn];

int real_id[maxn];

void go(int vx,int num,int p=-1){
	for(int i : L[vx])
		real_id[i] += num;
	debug("go %d with %d\n",vx,num);
	for(int i : L[vx])
		if(mrk[i] == 1 && i != p)
			go(i,2*num,vx);
}


void Bob( int V, int U, int C[], int D[] ){

	for(int i=0;i<U;i++){
		dg[C[i]]++, dg[D[i]]++;
		L[C[i]].pb(D[i]);
		L[D[i]].pb(C[i]);
	}

	vector<int> id;
	for(int i=0;i<V;i++)
		id.pb(i);
	sort(id.begin(), id.end(), [](int i,int j){
		return dg[i] > dg[j];
	});

	debug("id %d (%d), %d(%d)\n",id[0],dg[id[0]],id[1],dg[id[1]]);

	for(int i : L[id[0]])
		mrk[i]++;
	for(int i : L[id[1]])
		mrk[i]++;

	int ini;
	for(int i=0;i<V;i++) if(mrk[i] == 0 && i != id[0] && i != id[1]) ini = i;

	go(ini,1);

	for(int i=0;i<V;i++)
		debug("mrk[%d] = %d, real_id = %d\n",i,mrk[i],real_id[i]);

	vector<pii> ans	;
	for(int i=0;i<U;i++)
		if(mrk[C[i]] == 2 && mrk[D[i]] == 2){
			debug("add %d %d -> %d %d\n",C[i],D[i],real_id[C[i]], real_id[D[i]]);
			ans.pb({real_id[C[i]], real_id[D[i]]});
		}

	InitMap( V - 13, ans.size() );

	for(pii i : ans)

		MakeMap( i.first, i.second );

}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:70:4: warning: 'ini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |  go(ini,1);
      |  ~~^~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

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

Submission #313388

Compilation message

Subtask #1 22.0 / 22.0

Subtask #2 0 / 15.0

Subtask #3 0 / 63.0

Subtask #1
22.0 / 22.0

Subtask #2
0 / 15.0

Subtask #3
0 / 63.0