oj.uz

Submission #115015

# Submission time Handle Problem Language Result Execution time Memory
115015 2019-06-04T12:00:32 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 254 ms 9908 KB 
#include "highway.h"
#include <iostream>
using namespace std;
 
long long int allc,ta[1300005],m,p[1300005],amoney,bmoney,t,cnt,n,tag[1300005],road[1300005],map[2600005][2],sumlength,length,point,startans=-1,endans=-1,tree[1300005],trueroad,start=-1,a[1000005],father[1000005][2];
unsigned long long int check()
{
	vector<int> w(m);
	for(int i=0;i<m;i++)
	{
		w[i]=p[i];
		//if(allc==1)cout<<i<<" "<<w[i]<<" ";
	}
	long long int g=ask(w);
	//cout<<g<<endl;
	for(int i=0;i<m;i++)p[i]=0;
	return g;
}
unsigned long long int find(int s,int e)
{
	if(s==e)
	{
		start=s;
		return 0;
	}
	int mid=(s+e)/2;
	for(int i=s;i<=mid;i++)p[i]=1;
	t=check();
	if(t>cnt)find(s,mid);
	else find(mid+1,e);
	return 0;
}
unsigned long long int buildtree(int xx)
{
	int pt=1,ppt=1;
	ta[pt]=xx;
	while(pt<=ppt)
	{
		int x=ta[pt];
		int p=road[x];
		int c=0;
		while(p!=-1)
		{
			if(tag[map[p][0]]==0)
			{
				c=1;
				ppt++;
				tag[map[p][0]]=1;
				father[map[p][0]][0]=x;
				father[map[p][0]][1]=p/2;
				//buildtree(map[p][0]);
				ta[ppt]=map[p][0];
			}
			p=map[p][1];
		}
		if(c==0)
		{
			a[0]++;
			a[a[0]]=x;
		}
		pt++;
	}
	return 0;
}
unsigned long long int findroad(int xx)
{
	int tp=xx;
	while(tp!=point && p[father[tp][1]]==0)
	{
		p[father[tp][1]]=1;
	    tp=father[tp][0];
	}
	return 0;
}
unsigned long long int findtwo(int s,int e)
{
	//cout<<"二分"<<s<<" "<<e<<endl;
	//for(int i=s;i<=e;i++)cout<<a[i]<<" ";
	//cout<<endl;
	if(s==e)
	{
		trueroad=a[s];
		return 0;
	}
	for(int i=s;i<=(s+e)/2;i++)
	{
		findroad(a[i]);
	}
	long long int l=check();
	l=(l-cnt)/(bmoney-amoney);
	//if(l==cnt)findtwo((s+e)/2+1,e);
	//for(int i=(s+e)/2+1;i<=e;i++)findroad(a[i]);
	//int r=check();
	if(l==length)findtwo(s,(s+e)/2);
	else findtwo((s+e)/2+1,e);
	return 0;
}
unsigned long long int findlength(int x)
{
    int tp=x;
    while(tp!=point)
    {
        sumlength++;
        tp=father[tp][0];
    }
    return 0;
}
unsigned long long int findans(int x)
{
    int tp=x;
    while(length!=sumlength)
    {
        sumlength--;
        tp=father[tp][0];
    }
    if(startans==-1)startans=tp;
    else endans=tp;
    return 0;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	amoney=A;
	bmoney=B;
	n=N;
	for(int i=0;i<n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		map[i*2][0]=V[i];
		map[i*2][1]=road[U[i]];
		road[U[i]]=i*2;
		map[i*2+1][0]=U[i];
		map[i*2+1][1]=road[V[i]];
		road[V[i]]=i*2+1;
	}
	
	for(int i=0;i<m;i++)p[i]=0;
	cnt=check();
	
	find(0,m-1);
	//cout<<V[start]<<" "<<U[start]<<endl;
	tag[V[start]]=1;
	tag[U[start]]=1;
	point=U[start];
 
	buildtree(point);
 
	//cout<<endl;
	//cout<<point<<endl;
	for(int i=1;i<=a[0];i++)
	{
		//cout<<a[i]<<" ";
		findroad(a[i]);
	}
	length=(check()-cnt)/(bmoney-amoney);
	//cout<<endl;
	
	findtwo(1,a[0]);
	findlength(trueroad);
	//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
 
	findans(trueroad);
	
	
	
	point=V[start];
	a[0]=0;
	tag[point]=1;
	sumlength=0;
	buildtree(point);
	//cout<<endl;
	//cout<<point<<endl;
	//cout<<"第二個點"<<endl; 
	for(int i=1;i<=a[0];i++)
	{
		//cout<<a[i]<<" ";
		findroad(a[i]);
	}
	//cout<<endl;
	allc=1;
	length=check();
	length=(length-cnt)/(bmoney-amoney);
	allc=0;
	//cout<<length<<endl;
	//cout<<endl;
	findtwo(1,a[0]);
	findlength(trueroad);
	//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
 
	findans(trueroad);
	//cout<<startans<<" "<<endans<<endl;
	answer(startans,endans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 368 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 2 ms 444 KB Output is correct
8 Correct 2 ms 360 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 452 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 21 ms 1396 KB Output is correct
3 Correct 161 ms 9568 KB Output is correct
4 Correct 199 ms 9552 KB Output is correct
5 Correct 178 ms 9560 KB Output is correct
6 Correct 171 ms 9568 KB Output is correct
7 Correct 185 ms 9544 KB Output is correct
8 Correct 182 ms 9580 KB Output is correct
9 Correct 174 ms 9608 KB Output is correct
10 Correct 205 ms 9564 KB Output is correct
11 Correct 172 ms 8928 KB Output is correct
12 Correct 164 ms 9064 KB Output is correct
13 Correct 179 ms 9180 KB Output is correct
14 Correct 197 ms 9156 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1320 KB Output is correct
2 Correct 13 ms 2272 KB Output is correct
3 Correct 32 ms 3208 KB Output is correct
4 Correct 124 ms 8944 KB Output is correct
5 Correct 152 ms 8840 KB Output is correct
6 Correct 150 ms 9048 KB Output is correct
7 Correct 122 ms 9164 KB Output is correct
8 Correct 117 ms 9016 KB Output is correct
9 Correct 159 ms 9032 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 21 ms 1272 KB Output is correct
3 Correct 112 ms 7504 KB Output is correct
4 Correct 149 ms 9556 KB Output is correct
5 Correct 174 ms 9676 KB Output is correct
6 Correct 177 ms 9672 KB Output is correct
7 Correct 168 ms 9564 KB Output is correct
8 Correct 164 ms 9544 KB Output is correct
9 Correct 194 ms 9488 KB Output is correct
10 Correct 190 ms 9536 KB Output is correct
11 Correct 170 ms 9196 KB Output is correct
12 Correct 175 ms 9116 KB Output is correct
13 Correct 196 ms 9104 KB Output is correct
14 Correct 218 ms 8964 KB Output is correct
15 Correct 172 ms 9568 KB Output is correct
16 Correct 170 ms 9564 KB Output is correct
17 Correct 184 ms 9264 KB Output is correct
18 Correct 194 ms 9180 KB Output is correct
19 Correct 164 ms 9572 KB Output is correct
20 Correct 226 ms 9164 KB Output is correct
21 Correct 185 ms 9844 KB Output is correct
22 Correct 193 ms 9908 KB Output is correct
23 Correct 208 ms 9208 KB Output is correct
24 Correct 209 ms 9200 KB Output is correct
25 Correct 254 ms 9284 KB Output is correct

Subtask #5
0 / 18.0

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