Submission #56642

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

Alice

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

int cnt;
bool chk[1005];

void Alice (int N, int M, int A[], int B[]) {
	for(int i=0;i<M;i++) {
		if(max(A[i], B[i]) == min(A[i], B[i]) + 1) {
			chk[min(A[i], B[i])] = 1;
			cnt++;
		}
	}
	InitG(N+1, M+(N-1-cnt)*2+1);
	for(int i=0;i<M;i++) {
		MakeG(i, max(A[i], B[i]), min(A[i], B[i]));
	}
	for(int i=0,j=0;i<N-1;i++) {
		if(chk[i]) continue;
		MakeG(M+2*j, i+1, i);
		MakeG(M+2*j+1, N, i);
		j++;
	}
	MakeG(M+(N-1-cnt)*2, N, N-1);
}

Bob

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

int x[1005], y[1005], idg[1005], cc, cnt;
bool chk[1005];

vector<int> adj[1005];
queue<int> q;

void Bob (int V, int U, int C[], int D[]) {
	cc = V;
	for(int i=0;i<U;i++) {
		adj[C[i]].push_back(D[i]);
		idg[D[i]]++;
	}
	for(int i=0;i<V;i++) {
		if(idg[i] == 0) q.push(i);
	}
	while(!q.empty()) {
		int C = q.front();
		q.pop();
		x[C] = --cc;
		y[cc] = C;
		for(auto &T : adj[C]) {
			if(--idg[T] == 0) q.push(T);
		}
	}
	for(auto &T : adj[y[V-1]]) {
		if(x[T] != V-2) {
			chk[T] = true;
			cnt++;
		}
	}
	InitMap(V-1, U-2*cnt-1);
	for(int i=0;i<U;i++) {
		if(x[C[i]] == V-1) continue;
		if(!(x[C[i]] == x[D[i]]+1 && chk[D[i]])) {
			MakeMap(x[C[i]], x[D[i]]);
		}
	}
}

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