oj.uz

Submission #114921

# Submission time Handle Problem Language Result Execution time Memory
114921 2019-06-03T23:31:06 Z tutis Highway Tolls (IOI18_highway) C++17
51 / 100
 244 ms 10492 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();
	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[2] = {U[tarp[0]], V[tarp[0]]};
	int d[2][N];
	int pa[2][N];
	for (int t : {0, 1})
	{
		fill_n(d[t], N, N + 3);
		d[t][u[t]] = 0;
		queue<int>Q;
		Q.push(u[t]);
		while (!Q.empty())
		{
			int a = Q.front();
			Q.pop();
			for (int b : adj[a])
			{
				if (d[t][b] > d[t][a] + 1)
				{
					d[t][b] = d[t][a] + 1;
					Q.push(b);
				}
			}
		}
		for (int i = 0; i < M; i++)
		{
			if (d[t][U[i]] < d[t][V[i]])
				pa[t][V[i]] = i;
			if (d[t][U[i]] > d[t][V[i]])
				pa[t][U[i]] = i;
		}
	}
	ll d_st = maxi / ll(B);
	vector<int>v[2];
	for (int t : {0, 1})
	{
		for (int i = 0; i < N; i++)
		{
			if (d[t][i] < d[1 - t][i])
				v[t].push_back(i);
		}
	}
	fill_n(w.begin(), M, 1);
	for (int i : v[0])
	{
		if (i != u[0])
			w[pa[0][i]] = 0;
	}
	int d_s = ((maxi - ask(w)) / ll(B - A));
	int d_t = d_st - d_s - 1;
	vector<int>s, t;
	for (int i : v[0])
		if (d[0][i] == d_s)
			s.push_back(i);
	for (int i : v[1])
		if (d[1][i] == d_t)
			t.push_back(i);
	while (s.size() > 1)
	{
		vector<int>s1, s2;
		for (int i = 0; i < s.size(); i++)
		{
			if (i < s.size() / 2)
				s1.push_back(s[i]);
			else
				s2.push_back(s[i]);
		}
		fill_n(w.begin(), M, 1ll);
		for (int i : s1)
			w[pa[0][i]] = 0;
		if (ask(w) < maxi)
			s = s1;
		else
			s = s2;
	}
	while (t.size() > 1)
	{
		vector<int>t1, t2;
		for (int i = 0; i < t.size(); i++)
		{
			if (i < t.size() / 2)
				t1.push_back(t[i]);
			else
				t2.push_back(t[i]);
		}
		fill_n(w.begin(), M, 1ll);
		for (int i : t1)
			w[pa[1][i]] = 0;
		if (ask(w) < maxi)
			t = t1;
		else
			t = t2;
	}
	answer(s[0], t[0]);
}/*
int main()
{

}
/**/

Compilation message

highway.cpp:136:1: warning: "/*" within comment [-Wcomment]
 /**/
  
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tarp.size(); i++)
                   ~~^~~~~~~~~~~~~
highway.cpp:25:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < tarp.size() / 2)
        ~~^~~~~~~~~~~~~~~~~
highway.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~
highway.cpp:99:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < s.size() / 2)
        ~~^~~~~~~~~~~~~~
highway.cpp:115:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size(); i++)
                   ~~^~~~~~~~~~
highway.cpp:117:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < t.size() / 2)
        ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 404 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 248 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 396 KB Output is correct
2 Correct 23 ms 1380 KB Output is correct
3 Correct 172 ms 9584 KB Output is correct
4 Correct 201 ms 9576 KB Output is correct
5 Correct 205 ms 9584 KB Output is correct
6 Correct 183 ms 9568 KB Output is correct
7 Correct 197 ms 9568 KB Output is correct
8 Correct 201 ms 9576 KB Output is correct
9 Correct 179 ms 9580 KB Output is correct
10 Correct 176 ms 9596 KB Output is correct
11 Correct 198 ms 9360 KB Output is correct
12 Correct 186 ms 9476 KB Output is correct
13 Correct 204 ms 9580 KB Output is correct
14 Correct 208 ms 9528 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1320 KB Output is correct
2 Correct 31 ms 2308 KB Output is correct
3 Correct 57 ms 3292 KB Output is correct
4 Correct 162 ms 9360 KB Output is correct
5 Correct 174 ms 9400 KB Output is correct
6 Correct 162 ms 9684 KB Output is correct
7 Correct 145 ms 9480 KB Output is correct
8 Correct 151 ms 9356 KB Output is correct
9 Correct 153 ms 9484 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 396 KB Output is correct
2 Correct 44 ms 1328 KB Output is correct
3 Correct 137 ms 7744 KB Output is correct
4 Correct 196 ms 9640 KB Output is correct
5 Correct 191 ms 9556 KB Output is correct
6 Correct 197 ms 9628 KB Output is correct
7 Correct 193 ms 9596 KB Output is correct
8 Correct 170 ms 9588 KB Output is correct
9 Correct 209 ms 9548 KB Output is correct
10 Correct 202 ms 9584 KB Output is correct
11 Correct 211 ms 9508 KB Output is correct
12 Correct 193 ms 9608 KB Output is correct
13 Correct 223 ms 9492 KB Output is correct
14 Correct 210 ms 9224 KB Output is correct
15 Correct 215 ms 9604 KB Output is correct
16 Correct 164 ms 9592 KB Output is correct
17 Correct 205 ms 9488 KB Output is correct
18 Correct 165 ms 9484 KB Output is correct
19 Correct 191 ms 9580 KB Output is correct
20 Correct 244 ms 9480 KB Output is correct
21 Correct 171 ms 10464 KB Output is correct
22 Correct 188 ms 10492 KB Output is correct
23 Correct 204 ms 10288 KB Output is correct
24 Correct 224 ms 10152 KB Output is correct
25 Correct 226 ms 9532 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1352 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 Correct 26 ms 1380 KB Output is correct
2 Correct 24 ms 1428 KB Output is correct
3 Correct 222 ms 9768 KB Output is correct
4 Correct 224 ms 9964 KB Output is correct
5 Incorrect 224 ms 10160 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -