oj.uz

Submission #114915

# Submission time Handle Problem Language Result Execution time Memory
114915 2019-06-03T22:31:58 Z tutis Highway Tolls (IOI18_highway) C++17
51 / 100
 221 ms 14724 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
	vector<int>adj[N];
	int M = U.size();
	assert(M == N - 1);
	for (int i = 0; i < M; i++)
	{
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	vector<int>tarp;
	for (int i = 0; i < M; i++)
		tarp.push_back(i);
	vector<int>w(M, 1);
	ll maxi = ask(w);
	while (tarp.size() > 1)
	{
		vector<int>t1;
		vector<int>t2;
		for (int i = 0; i < tarp.size(); i++)
		{
			if (i < tarp.size() / 2)
				t1.push_back(tarp[i]);
			else
				t2.push_back(tarp[i]);
		}
		fill_n(w.begin(), M, 1);
		for (int i : t1)
			w[i] = 0;
		if (ask(w) < maxi)
			tarp = t1;
		else
			tarp = t2;
	}
	assert(tarp.size() == 1);
	int u = U[tarp[0]];
	int v = V[tarp[0]];
	int s = u;
	int t = v;
	for (pair<int, int>ab : {make_pair(u, v), make_pair(v, u)})
	{
		int a = ab.first;
		int b = ab.second;
		int d[N];
		fill_n(d, N, N + 3);
		d[a] = 0;
		function<void(int, int)>dfs = [&](int i, int p)
		{
			for (int j : adj[i])
			{
				if (j == p || d[j] <= d[i])
					continue;
				d[j] = d[i] + 1;
				dfs(j, i);
			}
		};
		dfs(a, b);
		int pa[N];
		fill_n(pa, N, -1);
		for (int i = 0; i < M; i++)
		{
			if (d[U[i]] > d[V[i]])
				swap(U[i], V[i]);
			if (d[V[i]] < N + 3)
			{
				pa[V[i]] = i;
			}
		}
		fill_n(w.begin(), M, 1);
		for (int i = 0; i < N; i++)
		{
			if (pa[i] != -1)
			{
				w[pa[i]] = 0;
			}
		}
		int de = (maxi - ask(w)) / (ll(B - A));
		vector<int>X;
		for (int i = 0; i < N; i++)
			if (d[i] == de)
				X.push_back(i);
		while (X.size() > 1)
		{
			vector<int>x1;
			vector<int>x2;
			for (int i = 0; i < X.size(); i++)
			{
				if (i < X.size() / 2)
					x1.push_back(X[i]);
				else
					x2.push_back(X[i]);
			}
			fill_n(w.begin(), M, 1);
			for (int i : x1)
				w[pa[i]] = 0;
			if (ask(w) < maxi)
				X = x1;
			else
				X = x2;
		}
		if (a == u)
			s = X[0];
		else
			t = X[0];
	}
	answer(s, t);
}/*
int main()
{

}
/**/

Compilation message

highway.cpp:116:1: warning: "/*" within comment [-Wcomment]
 /**/
  
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tarp.size(); i++)
                   ~~^~~~~~~~~~~~~
highway.cpp:26:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < tarp.size() / 2)
        ~~^~~~~~~~~~~~~~~~~
highway.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < X.size(); i++)
                    ~~^~~~~~~~~~
highway.cpp:92:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < X.size() / 2)
         ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 324 KB Output is correct
12 Correct 2 ms 320 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 16 ms 1276 KB Output is correct
3 Correct 181 ms 8508 KB Output is correct
4 Correct 165 ms 8496 KB Output is correct
5 Correct 189 ms 8512 KB Output is correct
6 Correct 193 ms 8492 KB Output is correct
7 Correct 221 ms 8508 KB Output is correct
8 Correct 178 ms 8496 KB Output is correct
9 Correct 180 ms 8588 KB Output is correct
10 Correct 182 ms 8620 KB Output is correct
11 Correct 192 ms 9360 KB Output is correct
12 Correct 185 ms 10328 KB Output is correct
13 Correct 163 ms 9792 KB Output is correct
14 Correct 200 ms 9876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1832 KB Output is correct
2 Correct 36 ms 3460 KB Output is correct
3 Correct 39 ms 4992 KB Output is correct
4 Correct 156 ms 12284 KB Output is correct
5 Correct 179 ms 12464 KB Output is correct
6 Correct 176 ms 13576 KB Output is correct
7 Correct 157 ms 14724 KB Output is correct
8 Correct 174 ms 12932 KB Output is correct
9 Correct 170 ms 13196 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 300 KB Output is correct
2 Correct 23 ms 1280 KB Output is correct
3 Correct 152 ms 6736 KB Output is correct
4 Correct 183 ms 8504 KB Output is correct
5 Correct 173 ms 8512 KB Output is correct
6 Correct 186 ms 8488 KB Output is correct
7 Correct 185 ms 8560 KB Output is correct
8 Correct 175 ms 8476 KB Output is correct
9 Correct 158 ms 8496 KB Output is correct
10 Correct 187 ms 8508 KB Output is correct
11 Correct 200 ms 9520 KB Output is correct
12 Correct 201 ms 10360 KB Output is correct
13 Correct 209 ms 10040 KB Output is correct
14 Correct 177 ms 9892 KB Output is correct
15 Correct 191 ms 8500 KB Output is correct
16 Correct 173 ms 8540 KB Output is correct
17 Correct 212 ms 9624 KB Output is correct
18 Correct 189 ms 10100 KB Output is correct
19 Correct 177 ms 8500 KB Output is correct
20 Correct 185 ms 10668 KB Output is correct
21 Correct 176 ms 9400 KB Output is correct
22 Correct 184 ms 9324 KB Output is correct
23 Correct 203 ms 9076 KB Output is correct
24 Correct 191 ms 9044 KB Output is correct
25 Correct 214 ms 14108 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 1244 KB Execution killed with signal 11 (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 19 ms 1320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -