oj.uz

Submission #372310

# Submission time Handle Problem Language Result Execution time Memory
372310 2021-02-27T15:38:46 Z hoaphat1 Airline Route Map (JOI18_airline) C++17
0 / 100
 752 ms 29372 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#include "Alicelib.h"
#include "Boblib.h"
 
void Alice( int N, int M, int A[], int B[] ) {
	if (N <= 2) {
		InitG(N, M);
		for (int i = 0; i < M; i++) MakeG(i, A[i], B[i]);
		return ;
	}
	vector<pair<int,int>> edges;
	for (int i = 0; i < M; i++) edges.emplace_back(A[i], B[i]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10; j++) if ((i + 1) >> j & 1) edges.emplace_back(N + j, i);
	}
	for (int i = 0; i < N; i++) {
		edges.emplace_back(N + 11, i);
		edges.emplace_back(N + 10, i);
	}
	for (int i = 1; i < 10; i++) edges.emplace_back(N + i - 1, N + i);
	for (int i = 1; i < 12; i++) if (i != 10) edges.emplace_back(N + i, N + 10);
	InitG(N + 12, (int) edges.size());
	for (int i = 0; i < (int) edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}
#include<bits/stdc++.h>
 
using namespace std;
 
#include "Alicelib.h"
#include "Boblib.h"
 
void Bob( int V, int U, int C[], int D[] ) {
	if (V <= 2) {
		InitMap(V, U);
		for (int i = 0; i < U; i++) MakeMap( C[i], D[i]);
		return ;
	}
	vector<pair<int,int>> edges;
	vector<int> cnt(V);
	vector<vector<int>> g(V);
	for (int i = 0; i < U; i++) {
		++cnt[C[i]]; ++cnt[D[i]];
		g[C[i]].push_back(D[i]);
		g[D[i]].push_back(C[i]);
	}
	int pos;
	for (int i = 0; i < V; i++) if (cnt[i] == V - 11) {
		pos = i;
		break;
	}
	vector<bool> old(V);
	for (auto& u : g[pos]) {
		old[u] = true;
	}
	vector<int> bit(10, -1);
	int last = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	vector<bool> kt(V);
	for (auto& to : g[last]) kt[to] = true;
	kt[last] = true;
	for (int i = 0; i < V; i++) if (!kt[i]) {
		bit[0] = i;
		break;
	}
	last = bit[0];
	for (int i = 1; i < 10; i++) {
		for (auto& to : g[last]) {
			if (!old[to]) {
				bit[i] = to;
				break;
			}
		}
		old[last] = true;
		if (bit[i] == -1) break;
		last = bit[i];
	}
	vector<int> p(V);
	for (int i = 0; i < 10; i++) {
		if (bit[i] == -1) break;
      	old[bit[i]] = false;
		for (auto& u : g[bit[i]]) {
			p[u] |= 1 << i;
		}
	}
	old[max_element(cnt.begin(), cnt.end()) - cnt.begin()] = false;
	for (int i = 0; i < V; i++) {
		if (old[i]) {
			for (auto& u : g[i]) {
				if (old[u] && p[i] < p[u]) edges.emplace_back(p[i] - 1, p[u] - 1);
			}
		}
	}
	InitMap(V - 12, (int) edges.size());
	for (auto&x : edges) MakeMap(x.first, x.second);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |  for (auto& u : g[pos]) {
      |                      ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4920 KB Output is correct
2 Correct 5 ms 4832 KB Output is correct
3 Correct 5 ms 4932 KB Output is correct
4 Correct 5 ms 4832 KB Output is correct
5 Correct 5 ms 4832 KB Output is correct
6 Correct 5 ms 4832 KB Output is correct
7 Correct 6 ms 4896 KB Output is correct
8 Incorrect 5 ms 4832 KB Wrong Answer [11]
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4920 KB Output is correct
2 Correct 5 ms 4832 KB Output is correct
3 Correct 5 ms 4932 KB Output is correct
4 Correct 5 ms 4832 KB Output is correct
5 Correct 5 ms 4832 KB Output is correct
6 Correct 5 ms 4832 KB Output is correct
7 Correct 6 ms 4896 KB Output is correct
8 Incorrect 5 ms 4832 KB Wrong Answer [11]
9 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 752 ms 29372 KB Wrong Answer [12]
2 Halted 0 ms 0 KB -