oj.uz

Submission #97107

# Submission time Handle Problem Language Result Execution time Memory
97107 2019-02-14T00:20:11 Z tincamatei Highway Tolls (IOI18_highway) C++14
51 / 100
 226 ms 9756 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 90000;
const int MAX_M = 130000;

struct Edge {
	int a, b;
	int other(int x) {
		return a ^ b ^ x;
	}
} edge[MAX_M];

vector<int> graph[MAX_N];
vector<pair<int, int> > tree[2];
bool viz[MAX_N];

void buildSmallTrees(int eid, const std::vector<int> &U,
                              const std::vector<int> &V) {
	int X, Y;
	for(int i = 0; i < U.size(); ++i) {
		edge[i] = {U[i], V[i]};

		graph[U[i]].push_back(i);
		graph[V[i]].push_back(i);
	}
	X = edge[eid].a, Y = edge[eid].b;

	deque<pair<int, int> > q;
	q.push_back(make_pair(X, 0));
	q.push_back(make_pair(Y, 1));
	tree[0].push_back(make_pair(X, eid));
	tree[1].push_back(make_pair(Y, eid));
	viz[X] = viz[Y] = true;


	while(!q.empty()) {
		int nod, t;
		nod = q.front().first;
		t = q.front().second;
		q.pop_front();
		
		for(auto it: graph[nod]) {
			int son = edge[it].other(nod);
			if(!viz[son]) {
				viz[son] = true;
				tree[t].push_back(make_pair(son, it));
				q.push_back(make_pair(son, t));
			}
		}
	}
}

int searchTree(int t, int M, long long refpath) {
	int st = -1, dr = tree[t].size();
	vector<int> w(M, 0);

	reverse(tree[t].begin(), tree[t].end());
	
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		for(int i = 0; i < M; ++i)
			w[i] = 1;
		for(int i = 0; i <= mid; ++i)
			w[tree[t][i].second] = 0;
		if(ask(w) < refpath)
			dr = mid;
		else
			st = mid;
	}
	return tree[t][dr].first;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	int st, dr;
	long long refPath;
	vector<int> w(M, 1);
	refPath = ask(w);

	st = -1, dr = M;
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		for(int i = 0; i <= mid; ++i)
			w[i] = 0;
		for(int i = mid + 1; i < M; ++i)
			w[i] = 1;

		if(ask(w) < refPath)
			dr = mid;
		else
			st = mid;
	}

	// Muchia (U[dr], V[dr]) face parte dintr-un drum sigur
	
	buildSmallTrees(dr, U, V);
	answer(searchTree(0, M, refPath), searchTree(1, M, refPath));
}

Compilation message

highway.cpp: In function 'void buildSmallTrees(int, const std::vector<int>&, const std::vector<int>&)':
highway.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); ++i) {
                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2452 KB Output is correct
2 Correct 4 ms 2448 KB Output is correct
3 Correct 4 ms 2444 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2436 KB Output is correct
6 Correct 4 ms 2440 KB Output is correct
7 Correct 4 ms 2436 KB Output is correct
8 Correct 4 ms 2448 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2532 KB Output is correct
11 Correct 4 ms 2568 KB Output is correct
12 Correct 4 ms 2448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2460 KB Output is correct
2 Correct 22 ms 3256 KB Output is correct
3 Correct 205 ms 9072 KB Output is correct
4 Correct 205 ms 9072 KB Output is correct
5 Correct 212 ms 9096 KB Output is correct
6 Correct 173 ms 8992 KB Output is correct
7 Correct 206 ms 9076 KB Output is correct
8 Correct 203 ms 9092 KB Output is correct
9 Correct 183 ms 9068 KB Output is correct
10 Correct 226 ms 9084 KB Output is correct
11 Correct 215 ms 9112 KB Output is correct
12 Correct 215 ms 9040 KB Output is correct
13 Correct 219 ms 8948 KB Output is correct
14 Correct 215 ms 9156 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3204 KB Output is correct
2 Correct 41 ms 3956 KB Output is correct
3 Correct 57 ms 4752 KB Output is correct
4 Correct 177 ms 9016 KB Output is correct
5 Correct 189 ms 9016 KB Output is correct
6 Correct 180 ms 9096 KB Output is correct
7 Correct 168 ms 8964 KB Output is correct
8 Correct 165 ms 9008 KB Output is correct
9 Correct 165 ms 9088 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2544 KB Output is correct
2 Correct 25 ms 3152 KB Output is correct
3 Correct 141 ms 7828 KB Output is correct
4 Correct 200 ms 9112 KB Output is correct
5 Correct 212 ms 9076 KB Output is correct
6 Correct 202 ms 9076 KB Output is correct
7 Correct 200 ms 9072 KB Output is correct
8 Correct 191 ms 9052 KB Output is correct
9 Correct 217 ms 9072 KB Output is correct
10 Correct 212 ms 9096 KB Output is correct
11 Correct 206 ms 9052 KB Output is correct
12 Correct 200 ms 8988 KB Output is correct
13 Correct 197 ms 9216 KB Output is correct
14 Correct 221 ms 9032 KB Output is correct
15 Correct 187 ms 8984 KB Output is correct
16 Correct 185 ms 9016 KB Output is correct
17 Correct 210 ms 9080 KB Output is correct
18 Correct 217 ms 8996 KB Output is correct
19 Correct 184 ms 9064 KB Output is correct
20 Correct 215 ms 8952 KB Output is correct
21 Correct 181 ms 9756 KB Output is correct
22 Correct 184 ms 9636 KB Output is correct
23 Correct 181 ms 9456 KB Output is correct
24 Correct 192 ms 9460 KB Output is correct
25 Correct 202 ms 9076 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3252 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3260 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -