Submission #503195

#	Time	Username	Problem	Language	Result	Execution time	Memory
503195		sidon	Airline Route Map (JOI18_airline)	C++17	100 / 100	815 ms	25536 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

void Alice(int N, int M, int *A, int *B) {
	vector<pair<int, int>> G;
	
	for(int i = 1; i <= N; ++i)
		for(int j = 0; j < 10; ++j)
			if((i >> j) & 1) G.emplace_back(N+j, i-1);

	for(int j = 0; j < N+10; ++j) G.emplace_back(0+j, N+11);
	for(int j = 0; j < 0+10; ++j) G.emplace_back(N+j, N+10);
	for(int j = 1; j < 0+10; ++j) G.emplace_back(N+j, N+j-1);

	InitG(N + 12, size(G) + M);

	for(int i = 0; i < M; ++i)
		MakeG(i, A[i], B[i]);

	for(auto &[u, v] : G) MakeG(M++, u, v);
}

Bob

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

void Bob(int N, int M, int *A, int *B){

	int org = 0, d[N] = {}, p[N] = {}, rt, f = -1;
	vector<int> G[N];

	for(int i = 0; i < M; ++i)
		G[A[i]].push_back(B[i]),
		G[B[i]].push_back(A[i]);

	for(int i = 0; i < N; ++i)
		if(size(G[i]) > size(G[org])) org = i;

	for(int u = 0; u < N; ++u) {
		bool ok = u == org;
		for(int v : G[org]) if(v == u) ok = 1;
		if(!ok) rt = u;
	}

	for(int u : G[rt]) ++d[u];
	for(int u : G[rt])
		for(int v : G[u]) if(d[v]) ++d[u];

	for(int u : G[rt]) {
		p[u] = p[rt] = p[org] = -2e5;
		if(d[u] < 3 && ((int)size(G[u]) - 3) == (N-11)/2)
			d[f = u] = 0;
	}

	for(int j = 0, nxt; j < 10; ++j, d[f] = 0, f = nxt)
		for(int v : G[f])
			d[v] ? nxt = v : p[v] += 1<<j;

	vector<pair<int, int>> E;

	for(int i = 0; i < M; ++i)
		if(min(p[A[i]], p[B[i]]) >= 0)
			E.emplace_back(p[A[i]]-1, p[B[i]]-1);

	InitMap(N-12, size(E));
	for(auto &[u, v] : E) MakeMap(u, v);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:33:17: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  for(int j = 0, nxt; j < 10; ++j, d[f] = 0, f = nxt)
      |                 ^~~
Bob.cpp:7:37: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
    7 |  int org = 0, d[N] = {}, p[N] = {}, rt, f = -1;
      |                                     ^~

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63