oj.uz

Submission #56642

# Submission time Handle Problem Language Result Execution time Memory
56642 2018-07-12T04:39:56 Z khsoo01 Airline Route Map (JOI18_airline) C++11
0 / 100
 610 ms 22536 KB 
#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);
}


#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6896 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6896 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 610 ms 22536 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -