oj.uz

Submission #118758

# Submission time Handle Problem Language Result Execution time Memory
118758 2019-06-19T16:27:49 Z Sorting Highway Tolls (IOI18_highway) C++14
12 / 100
 375 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 - 1;

	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5028 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5020 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5024 KB Output is correct
11 Correct 6 ms 4904 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5180 KB Output is correct
2 Correct 27 ms 6008 KB Output is correct
3 Correct 213 ms 14044 KB Output is correct
4 Correct 218 ms 14148 KB Output is correct
5 Correct 242 ms 14032 KB Output is correct
6 Correct 229 ms 14148 KB Output is correct
7 Correct 218 ms 14076 KB Output is correct
8 Correct 228 ms 14092 KB Output is correct
9 Correct 256 ms 14080 KB Output is correct
10 Correct 243 ms 14052 KB Output is correct
11 Correct 235 ms 15884 KB Output is correct
12 Correct 248 ms 16576 KB Output is correct
13 Correct 234 ms 16088 KB Output is correct
14 Correct 230 ms 15316 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 7076 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 5112 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 375 ms 262144 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 345 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -