oj.uz

Submission #62946

# Submission time Handle Problem Language Result Execution time Memory
62946 2018-07-31T03:28:16 Z kingpig9 Airline Route Map (JOI18_airline) C++11
0 / 100
 679 ms 31084 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 1010;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static bool exist1[MAXN];

void Alice (int N, int M, int A[], int B[]) {
	for (int i = 0; i < MAXN; i++) {
		exist1[i] = false;
	}
	vector<pii> edges = vector<pii> ();

	for (int i = 0; i < M; i++) {
		if (A[i] > B[i]) {
			swap(A[i], B[i]);
		}
		exist1[A[i]] |= (B[i] == A[i] + 1);
		edges.push_back({A[i], B[i]});
	}

	for (int i = 0; i < N - 1; i++) {
		if (!exist1[i]) {
			edges.push_back({i, i + 1});
			edges.push_back({i, N});
		}
	}
	edges.push_back({N - 1, N});

	InitG(N + 1, edges.size());
	for (int i = 0; i < edges.size(); i++) {
		MakeG(i, edges[i].fi, edges[i].se);
	}
}

#include <bits/stdc++.h>
#include "Boblib.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 1010;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static vector<int> adj[MAXN];
static int indeg[MAXN];
static int ind[MAXN];

void Bob (int N, int M, int C[], int D[]) {
	//toposort!
	for (int i = 0; i < MAXN; i++) {
		adj[i].clear();
		indeg[i] = 0;
		ind[i] = 0;
	}

	for (int i = 0; i < M; i++) {
		adj[C[i]].push_back(D[i]);
		indeg[D[i]]++;
	}

	//toposort
	vector<int> topo = vector<int> ();
	stack<int> stk = stack<int> ();

	for (int i = 0; i < N; i++) {
		if (indeg[i] == 0) {
			stk.push(i);
		}
	}

	while (!stk.empty()) {
		int x = stk.top();
		stk.pop();
		ind[x] = topo.size();
		topo.push_back(x);

		for (int y : adj[x]) {
			if (--indeg[y] == 0) {
				stk.push(y);
			}
		}
	}

	vector<pii> ans = vector<pii> ();
	int last = topo.back();
	for (int x : topo) {
		if (x == last) {
			break;
		}

		bool existlast = false;
		for (int y : adj[x]) {
			if (y == last) {
				existlast = true;
			} else if (y != topo[ind[x] + 1]) {
				ans.push_back(pii(ind[x], ind[y]));
			}
		}

		if (!existlast) {
			//then x, x + 1
			ans.push_back(pii(ind[x], ind[x] + 1));
		}
	}

	//FINAL ANSWERS!
	InitMap(N - 1, ans.size());
	for (pii p : ans) {
		MakeMap(p.fi, p.se);
	}
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges.size(); i++) {
                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6640 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 6640 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 679 ms 31084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -