oj.uz

Submission #114914

# Submission time Handle Problem Language Result Execution time Memory
114914 2019-06-03T22:27:05 Z tutis Highway Tolls (IOI18_highway) C++17
0 / 100
 829 ms 1800 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;
	}
	int u = U[tarp[0]];
	int v = V[tarp[1]];
	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:114: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:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < X.size(); i++)
                    ~~^~~~~~~~~~
highway.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < X.size() / 2)
         ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 496 KB Output is correct
2 Incorrect 20 ms 1248 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1800 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 Correct 3 ms 376 KB Output is correct
2 Incorrect 45 ms 1288 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 829 ms 1404 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 804 ms 1408 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -