Submission #152609

#	Time	Username	Problem	Language	Result	Execution time	Memory
152609		Dat160601	Airline Route Map (JOI18_airline)	C++17	0 / 100	935 ms	31024 KiB

Alice

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

int hav[1007];
vector < pair <int, int> > pend;

void Alice(int N, int M, int A[], int B[]){
	if(N == 1 && M == 0){
		InitG(1, 0);
		return;
	}
	for(int i = 0; i < N; i++) hav[i] = 0;
	for(int i = 0; i < M; i++){
		if(A[i] > B[i]) swap(A[i], B[i]);
		if(A[i] == B[i] - 1) hav[A[i]] = 1;
		pend.push_back(make_pair(A[i], B[i]));
	}
	for(int i = 0; i < N; i++){
		if(i == N - 1){
			pend.push_back(make_pair(i, N));
			continue;
		}
		if(hav[i]) continue;
		pend.push_back(make_pair(i, i+1));
		pend.push_back(make_pair(i, N));
	}
	InitG(N + 1, (int)pend.size());
	for(int i = 0; i < (int)pend.size(); i++){
		MakeG(i, pend[i].first, pend[i].second);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int deg[1007], cnt, num[1007], ok[1007];
vector <int> adj[1007];
vector < pair <int, int> > ans;
void Bob(int V, int U, int C[], int D[]){
	if(V == 1 && U == 0){
		InitMap(1, 0);
		return;
	}
	ans.clear();
	for(int i = 0; i < V; i++){
		num[i] = 0;
		adj[i].clear();
		deg[i] = 0;
		ok[i] = 0;
	}
	for(int i = 0; i < U; i++){
		deg[C[i]]++;
		adj[D[i]].pb(C[i]);
	}
	queue <int> q;
	while(!q.empty()) q.pop();
	for(int i = 0; i < V; i++){
		if(deg[i] == 0)  q.push(i);
	}
	cnt = V;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		num[u] = --cnt;
		for(int v : adj[u]){
			deg[v]--;
			if(deg[v] == 0){
				q.push(v);
			}
		}
	}
	for(int i = 0; i < U; i++){
		C[i] = num[C[i]];
		D[i] = num[D[i]];
		if(D[i] == V-1) ok[C[i]] = 1;
	}
	for(int i = 0; i < U; i++){
		if(D[i] == V - 1 || C[i] == V - 1) continue;
		if(abs(D[i] - C[i]) == 1){
			if((C[i] < D[i] && ok[C[i]] == 1) || (C[i] > D[i] && ok[D[i]] == 1)) continue;
		}
		ans.pb(mp(C[i], D[i]));
	}
	InitMap(V - 1, (int)ans.size());
	for(int i = 0; i < (int)ans.size(); i++){
		MakeMap(ans[i].fi, ans[i].se);
	}
}

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