oj.uz

Submission #300655

# Submission time Handle Problem Language Result Execution time Memory
300655 2020-09-17T11:06:19 Z ElyesChaabouni Highway Tolls (IOI18_highway) C++14
51 / 100
 162 ms 9456 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int> >v[90005];
bool vu[90005];
/*int ask(vector<int>w)
{
	for(int i = 0; i < w.size(); i++)
		cout << w[i] << ' ';
	int x;
	cin >> x;
	return x;
}
void answer(int a, int b)
{
	cout << "ANSWR:\n" << a << ' ' << b;
}*/
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	vector<int>w(M);
	for(int i = 0; i < M; i++)
		w[i]=0;
	long long x=ask(w);
	int l=0, r=M-1;
	while(l != r)
	{
		int med=(l+r)/2;
		for(int i = 0; i <= med; i++)
			w[i]=1;
		long long cu = ask(w);
		if(cu!=x)
			r=med;
		else
			l=med+1;
		for(int i = 0; i <= med; i++)
			w[i]=0;
	}
	//cout << l << '\n';
	for(int i = 0; i < M; i++)
	{
		v[U[i]].push_back(make_pair(V[i], i));
		v[V[i]].push_back(make_pair(U[i], i));
	}
	for(int i = 0; i < 90005; i++)
		vu[i]=0;
	vector<pair<int, int> >bfs;
	vu[U[l]]=1;
	for(int i = 0; i < v[U[l]].size(); i++)
	{
		if(v[U[l]][i].second!=l)
		{
			bfs.push_back(v[U[l]][i]);
			vu[v[U[l]][i].first]=1;
		}
	}
	for(int i = 0; i < bfs.size(); i++)
	{
		for(int j = 0; j < v[bfs[i].first].size(); j++)
		{
			if(!vu[v[bfs[i].first][j].first] && v[bfs[i].first][j].first != ((bfs[i].first^U[bfs[i].second])^V[bfs[i].second]))
			{
				bfs.push_back(v[bfs[i].first][j]);
				vu[v[bfs[i].first][j].first]=1;
			}
		}
	}
	/*for(int i = 0; i < bfs.size(); i++)
	    cout << bfs[i].first << ' ';
	cout << '\n';*/
	for(int i = 0; i < w.size(); i++)
		w[i]=0;
  	for(int i = 0; i < bfs.size(); i++)
  {
	    //cout << bfs[i].first << ' ';
      //vu[bfs[i].first]=1;
  }
	for(int i = 0; i < M; i++)
	{
		if(vu[U[i]] && vu[V[i]])
			w[i]=1;
	}
	long long cu1=ask(w);
	int node1, node2;
	if(cu1==x)
	{
		node1=U[l];
	}
	else
	{
		int l1=0;
		int r1=bfs.size()-1;
		while(l1 != r1)
		{
			int med=(l1+r1)/2;
			for(int i = 0; i <= med; i++)
				w[bfs[i].second]=0;
			long long cu11=ask(w);
			if(cu11==x)
				r1=med;
			else
				l1=med+1;
			for(int i = 0; i <= med; i++)
				w[bfs[i].second]=1;
		}
		node1=bfs[l1].first;
	}
	bfs.clear();
	for(int i = 0; i < 90005; i++)
		vu[i]=0;
	vu[V[l]]=1;
	for(int i = 0; i < v[V[l]].size(); i++)
	{
		if(v[V[l]][i].second != l)
		{
			bfs.push_back(v[V[l]][i]);
			vu[v[V[l]][i].first]=1;
		}
	}
	for(int i = 0; i < bfs.size(); i++)
	{
		for(int j = 0; j < v[bfs[i].first].size(); j++)
		{
			if(!vu[v[bfs[i].first][j].first] && v[bfs[i].first][j].first != (bfs[i].first^U[bfs[i].second]^V[bfs[i].second]))
			{
				bfs.push_back(v[bfs[i].first][j]);
				vu[v[bfs[i].first][j].first]=1;
			}
		}
	}
	/*for(int i = 0; i < bfs.size(); i++)
  {
	    cout << bfs[i].first << ' ';
      vu[bfs[i].first]=1;
  }*/
	//cout << '\n';
	for(int i = 0; i < w.size(); i++)
		w[i]=0;
	for(int i = 0; i < M; i++)
	{
		if(vu[U[i]] && vu[V[i]])
			w[i]=1;
	}
  //cout << "here\n";
	cu1=ask(w);
	if(cu1==x)
	{
		node2=V[l];
	}
	else
	{
		int l1=0;
		int r1=bfs.size()-1;
		while(l1 != r1)
		{
			int med=(l1+r1)/2;
			for(int i = 0; i <= med; i++)
				w[bfs[i].second]=0;
			long long cu11=ask(w);
			if(cu11==x)
				r1=med;
			else
				l1=med+1;
			for(int i = 0; i <= med; i++)
				w[bfs[i].second]=1;
		}
		node2=bfs[l1].first;
	}
	answer(node1, node2);
}
/*int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	find_pair(7, {0, 1, 2, 5, 7, 5, 3, 3}, {2, 2, 5, 8, 5, 6, 2, 4}, 1, 2);
}*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0; i < v[U[l]].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < bfs.size(); i++)
      |                 ~~^~~~~~~~~~~~
highway.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j = 0; j < v[bfs[i].first].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0; i < w.size(); i++)
      |                 ~~^~~~~~~~~~
highway.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int i = 0; i < bfs.size(); i++)
      |                   ~~^~~~~~~~~~~~
highway.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0; i < v[V[l]].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(int i = 0; i < bfs.size(); i++)
      |                 ~~^~~~~~~~~~~~
highway.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int j = 0; j < v[bfs[i].first].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i = 0; i < w.size(); i++)
      |                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2560 KB Output is correct
2 Correct 2 ms 2560 KB Output is correct
3 Correct 2 ms 2560 KB Output is correct
4 Correct 2 ms 2560 KB Output is correct
5 Correct 2 ms 2560 KB Output is correct
6 Correct 2 ms 2496 KB Output is correct
7 Correct 2 ms 2560 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2560 KB Output is correct
10 Correct 2 ms 2560 KB Output is correct
11 Correct 2 ms 2560 KB Output is correct
12 Correct 2 ms 2560 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 15 ms 3328 KB Output is correct
3 Correct 152 ms 8932 KB Output is correct
4 Correct 152 ms 8840 KB Output is correct
5 Correct 155 ms 8804 KB Output is correct
6 Correct 141 ms 8860 KB Output is correct
7 Correct 156 ms 8856 KB Output is correct
8 Correct 148 ms 8932 KB Output is correct
9 Correct 133 ms 8808 KB Output is correct
10 Correct 148 ms 8836 KB Output is correct
11 Correct 154 ms 7824 KB Output is correct
12 Correct 159 ms 8288 KB Output is correct
13 Correct 135 ms 8300 KB Output is correct
14 Correct 149 ms 8284 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3200 KB Output is correct
2 Correct 26 ms 3936 KB Output is correct
3 Correct 37 ms 4448 KB Output is correct
4 Correct 108 ms 7800 KB Output is correct
5 Correct 115 ms 7804 KB Output is correct
6 Correct 115 ms 8240 KB Output is correct
7 Correct 109 ms 8256 KB Output is correct
8 Correct 106 ms 7932 KB Output is correct
9 Correct 112 ms 8448 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2672 KB Output is correct
2 Correct 15 ms 3200 KB Output is correct
3 Correct 102 ms 7656 KB Output is correct
4 Correct 143 ms 8808 KB Output is correct
5 Correct 134 ms 8928 KB Output is correct
6 Correct 133 ms 8808 KB Output is correct
7 Correct 137 ms 8936 KB Output is correct
8 Correct 138 ms 8804 KB Output is correct
9 Correct 145 ms 8932 KB Output is correct
10 Correct 150 ms 8908 KB Output is correct
11 Correct 153 ms 8288 KB Output is correct
12 Correct 154 ms 8240 KB Output is correct
13 Correct 162 ms 8292 KB Output is correct
14 Correct 151 ms 7908 KB Output is correct
15 Correct 131 ms 8800 KB Output is correct
16 Correct 136 ms 8820 KB Output is correct
17 Correct 154 ms 8288 KB Output is correct
18 Correct 144 ms 8288 KB Output is correct
19 Correct 136 ms 8764 KB Output is correct
20 Correct 156 ms 8200 KB Output is correct
21 Correct 133 ms 9456 KB Output is correct
22 Correct 118 ms 9324 KB Output is correct
23 Correct 136 ms 8540 KB Output is correct
24 Correct 138 ms 8532 KB Output is correct
25 Correct 155 ms 8420 KB Output is correct

Subtask #5
0 / 18.0

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