Submission #44955

#	Time	Username	Problem	Language	Result	Execution time	Memory
44955		Dat160601	Airline Route Map (JOI18_airline)	C++17	0 / 100	668 ms	30640 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) continue;
		if(D[i]==C[i]+1){
			if(ok[C[i]]) 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