oj.uz

Submission #300661

# Submission time Handle Problem Language Result Execution time Memory
300661 2020-09-17T11:17:28 Z ElyesChaabouni Highway Tolls (IOI18_highway) C++14
51 / 100
 235 ms 9384 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[node1]=1;
	for(int i = 0; i < v[node1].size(); i++)
	{
			bfs.push_back(v[node1][i]);
			vu[v[node1][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]=1;
  //cout << "here\n";
	if(1)
	{
		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[node1].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
highway.cpp:118: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]
  118 |  for(int i = 0; i < bfs.size(); i++)
      |                 ~~^~~~~~~~~~~~
highway.cpp:120: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]
  120 |   for(int j = 0; j < v[bfs[i].first].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  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 2688 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 2560 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 17 ms 3456 KB Output is correct
3 Correct 172 ms 8804 KB Output is correct
4 Correct 146 ms 8756 KB Output is correct
5 Correct 141 ms 8836 KB Output is correct
6 Correct 159 ms 8808 KB Output is correct
7 Correct 152 ms 8848 KB Output is correct
8 Correct 143 ms 8848 KB Output is correct
9 Correct 163 ms 8936 KB Output is correct
10 Correct 149 ms 8868 KB Output is correct
11 Correct 175 ms 8232 KB Output is correct
12 Correct 174 ms 8284 KB Output is correct
13 Correct 152 ms 8300 KB Output is correct
14 Correct 176 ms 8288 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 35 ms 3960 KB Output is correct
3 Correct 39 ms 4576 KB Output is correct
4 Correct 121 ms 8228 KB Output is correct
5 Correct 148 ms 8436 KB Output is correct
6 Correct 118 ms 8236 KB Output is correct
7 Correct 114 ms 8256 KB Output is correct
8 Correct 130 ms 8356 KB Output is correct
9 Correct 114 ms 8320 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 16 ms 3328 KB Output is correct
3 Correct 135 ms 7656 KB Output is correct
4 Correct 144 ms 8804 KB Output is correct
5 Correct 152 ms 8756 KB Output is correct
6 Correct 138 ms 8832 KB Output is correct
7 Correct 143 ms 8808 KB Output is correct
8 Correct 166 ms 9056 KB Output is correct
9 Correct 175 ms 8804 KB Output is correct
10 Correct 159 ms 8932 KB Output is correct
11 Correct 235 ms 8292 KB Output is correct
12 Correct 158 ms 8324 KB Output is correct
13 Correct 223 ms 8224 KB Output is correct
14 Correct 176 ms 8208 KB Output is correct
15 Correct 132 ms 8808 KB Output is correct
16 Correct 135 ms 8812 KB Output is correct
17 Correct 182 ms 8288 KB Output is correct
18 Correct 177 ms 8288 KB Output is correct
19 Correct 153 ms 8756 KB Output is correct
20 Correct 142 ms 8272 KB Output is correct
21 Correct 157 ms 9384 KB Output is correct
22 Correct 184 ms 9324 KB Output is correct
23 Correct 147 ms 8992 KB Output is correct
24 Correct 138 ms 9032 KB Output is correct
25 Correct 168 ms 8312 KB Output is correct

Subtask #5
0 / 18.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 -

Subtask #6
0 / 31.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 -