oj.uz

Submission #97108

# Submission time Handle Problem Language Result Execution time Memory
97108 2019-02-14T00:29:08 Z tincamatei Highway Tolls (IOI18_highway) C++14
51 / 100
 228 ms 9772 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, 0);
	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] = 1;
		for(int i = mid + 1; i < M; ++i)
			w[i] = 0;

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

	// Muchia (U[dr], V[dr]) face parte dintr-un drum sigur
	
	refPath = refPath / A * B;
	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 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2528 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2440 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2344 KB Output is correct
11 Correct 4 ms 2440 KB Output is correct
12 Correct 4 ms 2440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2544 KB Output is correct
2 Correct 28 ms 3152 KB Output is correct
3 Correct 185 ms 9072 KB Output is correct
4 Correct 206 ms 9092 KB Output is correct
5 Correct 199 ms 9076 KB Output is correct
6 Correct 209 ms 9068 KB Output is correct
7 Correct 198 ms 9072 KB Output is correct
8 Correct 205 ms 9072 KB Output is correct
9 Correct 204 ms 9156 KB Output is correct
10 Correct 183 ms 9076 KB Output is correct
11 Correct 200 ms 9128 KB Output is correct
12 Correct 208 ms 9052 KB Output is correct
13 Correct 213 ms 8960 KB Output is correct
14 Correct 221 ms 9096 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3156 KB Output is correct
2 Correct 50 ms 3956 KB Output is correct
3 Correct 67 ms 4820 KB Output is correct
4 Correct 162 ms 9020 KB Output is correct
5 Correct 191 ms 9008 KB Output is correct
6 Correct 166 ms 9028 KB Output is correct
7 Correct 188 ms 8996 KB Output is correct
8 Correct 177 ms 9048 KB Output is correct
9 Correct 172 ms 9152 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2540 KB Output is correct
2 Correct 43 ms 3212 KB Output is correct
3 Correct 176 ms 7844 KB Output is correct
4 Correct 186 ms 9072 KB Output is correct
5 Correct 197 ms 9140 KB Output is correct
6 Correct 194 ms 9020 KB Output is correct
7 Correct 198 ms 9080 KB Output is correct
8 Correct 184 ms 9072 KB Output is correct
9 Correct 198 ms 9140 KB Output is correct
10 Correct 202 ms 9176 KB Output is correct
11 Correct 210 ms 8980 KB Output is correct
12 Correct 207 ms 9000 KB Output is correct
13 Correct 199 ms 9200 KB Output is correct
14 Correct 221 ms 9024 KB Output is correct
15 Correct 186 ms 8992 KB Output is correct
16 Correct 194 ms 9076 KB Output is correct
17 Correct 202 ms 9080 KB Output is correct
18 Correct 228 ms 8976 KB Output is correct
19 Correct 176 ms 9060 KB Output is correct
20 Correct 211 ms 9004 KB Output is correct
21 Correct 182 ms 9712 KB Output is correct
22 Correct 171 ms 9772 KB Output is correct
23 Correct 193 ms 9496 KB Output is correct
24 Correct 178 ms 9416 KB Output is correct
25 Correct 207 ms 9072 KB Output is correct

Subtask #5
0 / 18.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 -

Subtask #6
0 / 31.0

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