Submission #44121

#	Time	Username	Problem	Language	Result	Execution time	Memory
44121		khsoo01	Airline Route Map (JOI18_airline)	C++11	0 / 100	666 ms	22760 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] ){
	int CEI = 0;
	if(N <= 2) {
		InitG(N, M);
		for(int i=0;i<M;i++) {
			MakeG(i, A[i], B[i]);
		}
		return;
	}
	int PCS = 0;
	for(int i=0;i<N;i++) {
		PCS += __builtin_popcount(i);
	}
	InitG(N+12, M+2*N+10+PCS);
	for(int i=0;i<M;i++) {
		MakeG(CEI++, A[i], B[i]);
	}
	for(int i=0;i<N;i++) {
		MakeG(CEI++, N+10, i);
	}
	for(int i=0;i<N;i++) {
		MakeG(CEI++, N+11, i);
	}
	MakeG(CEI++, N+11, N);
	for(int i=0;i<10;i++) {
		if(i+1<10) MakeG(CEI++, N+i, N+i+1);
		for(int j=0;j<N;j++) {
			if(j & (1<<i)) MakeG(CEI++, N+i, j);
		}
	}
}

Bob

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

const int MN = 2005;

int n, m, p1, p2, idx[MN];
bool in[MN];

vector<int> adj[MN];

void Bob(int V, int U, int C[], int D[] ){
	if(V <= 2) {
		InitMap(V, U);
		for(int i=0;i<U;i++) {
			MakeMap(C[i], D[i]);
		}
		return;
	}
	n = V - 12;
	int PCS = 0;
	for(int i=0;i<n;i++) {
		PCS += __builtin_popcount(i);
	}
	m = U - 2*n - 10 - PCS;
	InitMap(n, m);
	for(int i=0;i<U;i++) {
		adj[C[i]].push_back(D[i]);
	}
	for(int i=0;i<V;i++) {
		if(adj[i].size() == n) p1 = i;
		if(adj[i].size() == n+1) p2 = i;
	}
	for(auto &T : adj[p1]) in[T] = true;
	int X = 0;
	for(auto &T : adj[p2]) if(!in[T]) X = T;
	for(int Y = -1, i = 0; ~X ; X = Y, Y = -1, i++) {
		for(auto &T : adj[X]) {
			if(!in[T]) {Y = T; continue;}
			idx[T] += (1<<i);
		}
	}
	for(int i=0;i<V;i++) {
		if(!in[i]) continue;
		for(auto &T : adj[i]) {
			MakeMap(idx[i], idx[T]);
		}
	}
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(adj[i].size() == n) p1 = i;
      ~~~~~~~~~~~~~~^~~~
Bob.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(adj[i].size() == n+1) p2 = i;
      ~~~~~~~~~~~~~~^~~~~~

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