oj.uz

Submission #116500

# Submission time Handle Problem Language Result Execution time Memory
116500 2019-06-12T15:56:55 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 243 ms 10724 KB 
#include "highway.h"
#include <iostream>
using namespace std;

unsigned long long int tree[900005][2],t[1000005][2],father[900005][2],cnt,road[900005],map[2600005][2],m,p[1300005];
long long int check()
{
	vector<int> w(m);
	for(int i=0;i<m;i++)w[i]=p[i];
	for(int i=0;i<m;i++)p[i]=1;
	return ask(w);
}
void find_pair(int n,vector<int> u,vector<int> v,int a, int b) {
	m=u.size();
	for(int i=0;i<n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		int x=u[i],y=v[i];
		map[i*2][0]=x;
		map[i*2][1]=road[y];
		road[y]=i*2;
		map[i*2+1][0]=y;
		map[i*2+1][1]=road[x];
		road[x]=i*2+1;
	}
	for(int i=0;i<m;i++)p[i]=1;
	cnt=check();
	//cout<<cnt<<endl;
	int point;
	int l=0,r=m-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		for(int i=l;i<=mid;i++)p[i]=0;
		long long int tmp=check();
		if(tmp<cnt)
		{
			r=mid-1;
			point=mid;
		}
		else l=mid+1;
	}
	long long int start=u[point];
	long long int end=v[point];
	int tp=1,tpp=2;
	t[1][0]=start;
	t[1][1]=0;
	t[2][0]=end;
	t[2][1]=1;
	tree[0][0]++;
	tree[0][1]++;
	tree[1][0]=start;
	tree[1][1]=end;
	for(int i=0;i<n;i++)father[i][0]=-2;
	father[start][0]=-1;
	father[start][1]=130000;
	father[end][0]=-1;
	father[end][1]=130000;
	while(tp<=tpp)
	{
		int now=t[tp][0];
		int g=road[now];
		while(g!=-1)
		{
			if(father[map[g][0]][0]==-2)
			{
				father[map[g][0]][0]=now;
				father[map[g][0]][1]=g/2;
				tpp++;
				t[tpp][0]=map[g][0];
				t[tpp][1]=t[tp][1];
				tree[0][t[tp][1]]++;
				tree[tree[0][t[tp][1]]][t[tp][1]]=map[g][0];
			}
			g=map[g][1];
		}
		tp++;
	}
	for(int i=1;i<=tree[0][0];i++)
	{
		int g=tree[i][0];
		//cout<<tree[i][0]<<" "; 
		while(p[father[g][1]]==1)
		{
			p[father[g][1]]=0;
			g=father[g][0];
		}
	}
	//cout<<endl;
	cnt=check();
	l=1,r=tree[0][0];
	int startans;
	while(l<=r)
	{
		int mid=(l+r)/2;
		for(int i=l;i<=mid;i++)
		{
			int g=tree[i][0];
			while(p[father[g][1]]==1)
			{
				p[father[g][1]]=0;
				g=father[g][0];
			}
		}
		long long int tmp=check();
		if(tmp==cnt)
		{
			startans=tree[mid][0];
			r=mid-1;
		}
		else l=mid+1;
	}
	for(int i=1;i<=tree[0][1];i++)
	{
		int g=tree[i][1];
		while(p[father[g][1]]==1)
		{
			p[father[g][1]]=0;
			g=father[g][0];
		}
	}
	//cout<<endl;
	cnt=check();
	//cout<<cnt<<endl;
	l=1,r=tree[0][1];
	int endans;
	while(l<=r)
	{
		int mid=(l+r)/2;
		//cout<<l<<" "<<r<<endl;
		for(int i=l;i<=mid;i++)
		{
			int g=tree[i][1];
			while(p[father[g][1]]==1)
			{
				//cout<<father[g][1]<<" ";
				p[father[g][1]]=0;
				g=father[g][0];
			}
		}
		//cout<<endl;
		long long int tmp=check();
		//cout<<tmp<<endl;
		if(tmp==cnt)
		{
			endans=tree[mid][1];
			r=mid-1;
		}
		else l=mid+1;
	}
	//cout<<startans<<" "<<endans<<endl;
	answer(startans,endans);
}

Compilation message

highway.cpp: In function 'long long int check()':
highway.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<m;i++)w[i]=p[i];
              ~^~
highway.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<m;i++)p[i]=1;
              ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<m;i++)
              ~^~
highway.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<m;i++)p[i]=1;
              ~^~
highway.cpp:36:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(tmp<cnt)
      ~~~^~~~
highway.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(father[map[g][0]][0]==-2)
       ~~~~~~~~~~~~~~~~~~~~^~~~
highway.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=tree[0][0];i++)
              ~^~~~~~~~~~~~
highway.cpp:106:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(tmp==cnt)
      ~~~^~~~~
highway.cpp:113:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=tree[0][1];i++)
              ~^~~~~~~~~~~~
highway.cpp:144:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(tmp==cnt)
      ~~~^~~~~
highway.cpp:152:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:152:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:43:29: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
  long long int start=u[point];
                             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 296 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 22 ms 1404 KB Output is correct
3 Correct 163 ms 10612 KB Output is correct
4 Correct 209 ms 10588 KB Output is correct
5 Correct 195 ms 10600 KB Output is correct
6 Correct 181 ms 10608 KB Output is correct
7 Correct 201 ms 10600 KB Output is correct
8 Correct 161 ms 10636 KB Output is correct
9 Correct 190 ms 10600 KB Output is correct
10 Correct 192 ms 10608 KB Output is correct
11 Correct 187 ms 10020 KB Output is correct
12 Correct 216 ms 10300 KB Output is correct
13 Correct 217 ms 10584 KB Output is correct
14 Correct 204 ms 10496 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1400 KB Output is correct
2 Correct 42 ms 2588 KB Output is correct
3 Correct 60 ms 3728 KB Output is correct
4 Correct 172 ms 10064 KB Output is correct
5 Correct 163 ms 10144 KB Output is correct
6 Correct 193 ms 10456 KB Output is correct
7 Correct 187 ms 10548 KB Output is correct
8 Correct 189 ms 10204 KB Output is correct
9 Correct 139 ms 10252 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 15 ms 1400 KB Output is correct
3 Correct 128 ms 8340 KB Output is correct
4 Correct 157 ms 10668 KB Output is correct
5 Correct 184 ms 10616 KB Output is correct
6 Correct 151 ms 10620 KB Output is correct
7 Correct 181 ms 10604 KB Output is correct
8 Correct 179 ms 10712 KB Output is correct
9 Correct 202 ms 10524 KB Output is correct
10 Correct 190 ms 10580 KB Output is correct
11 Correct 216 ms 10688 KB Output is correct
12 Correct 215 ms 10404 KB Output is correct
13 Correct 200 ms 10324 KB Output is correct
14 Correct 232 ms 10116 KB Output is correct
15 Correct 188 ms 10604 KB Output is correct
16 Correct 137 ms 10724 KB Output is correct
17 Correct 182 ms 10496 KB Output is correct
18 Correct 186 ms 10648 KB Output is correct
19 Correct 200 ms 10680 KB Output is correct
20 Correct 220 ms 10516 KB Output is correct
21 Correct 188 ms 10704 KB Output is correct
22 Correct 181 ms 10608 KB Output is correct
23 Correct 194 ms 9896 KB Output is correct
24 Correct 200 ms 9920 KB Output is correct
25 Correct 243 ms 10476 KB Output is correct

Subtask #5
0 / 18.0

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