oj.uz

Submission #118754

# Submission time Handle Problem Language Result Execution time Memory
118754 2019-06-19T16:23:14 Z Sorting Highway Tolls (IOI18_highway) C++14
0 / 100
 377 ms 262148 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

const int MAXN = 1e5 + 7;

mt19937 mt();

long long n, m;
vector<int> adj[MAXN], idx[MAXN], w;
vector<pair<int, int> > e;
int depth[MAXN];

void dfs(int u, int pr = -1, int d = 0){
	depth[u] = d;
	for(int i = 0; i < adj[u].size(); i++){
		int to = adj[u][i], j = idx[u][i];

		if(to == pr){
			continue;
		}

		e.push_back({d + 1, j});
		dfs(to, u, d + 1);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	n = N;
	m = U.size();

	for(int i = 0; i < m; i++){
		adj[V[i]].push_back(U[i]);
		adj[U[i]].push_back(V[i]);

		idx[V[i]].push_back(i);
		idx[U[i]].push_back(i);
		w.push_back(0);
	}

	long long a = A, b = B;
	long long sm = ask(w);

	dfs(0);

	sort(e.begin(), e.end());

	int l = 0, r = m;

	while(l != r){
		int mid = (l + r) / 2;

		for(int i = 0; i < m; i++){
			w[i] = 0;
		}
		for(int i = mid + 1; i <= r; i++){
			w[e[i].second] = true;
		}

		long long score = ask(w);
		score -= sm;

		if(score){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}

	int x = V[e[l].second], y = U[e[l].second];

	if(depth[x] < depth[y]){
		swap(x, y);
	}

	answer(0, x);
}

/*
9 1 2
4 8
4 2
8 0
2 5
2 7
2 3
0 1
0 6
*/

Compilation message

highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++){
                 ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:12: warning: unused variable 'a' [-Wunused-variable]
  long long a = A, b = B;
            ^
highway.cpp:42:19: warning: unused variable 'b' [-Wunused-variable]
  long long a = A, b = B;
                   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5104 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5084 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5020 KB Output is correct
7 Correct 6 ms 5008 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5032 KB Output is correct
11 Correct 6 ms 5028 KB Output is correct
12 Incorrect 6 ms 4984 KB Output is incorrect: {s, t} is wrong.

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5108 KB Output is correct
2 Correct 20 ms 6108 KB Output is correct
3 Correct 233 ms 14048 KB Output is correct
4 Correct 220 ms 14044 KB Output is correct
5 Correct 249 ms 14044 KB Output is correct
6 Correct 229 ms 14048 KB Output is correct
7 Correct 242 ms 14200 KB Output is correct
8 Correct 231 ms 14032 KB Output is correct
9 Correct 218 ms 14036 KB Output is correct
10 Correct 234 ms 14124 KB Output is correct
11 Correct 242 ms 15956 KB Output is correct
12 Correct 224 ms 16672 KB Output is correct
13 Correct 234 ms 16168 KB Output is correct
14 Incorrect 220 ms 15316 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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