oj.uz

Submission #115014

# Submission time Handle Problem Language Result Execution time Memory
115014 2019-06-04T11:58:56 Z tinjyu Highway Tolls (IOI18_highway) C++14
11 / 100
 214 ms 9648 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]);
	}
	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 376 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 360 KB Output is correct
7 Correct 2 ms 376 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 364 KB Output is correct
11 Correct 2 ms 276 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 20 ms 1396 KB Output is correct
3 Correct 181 ms 9560 KB Output is correct
4 Correct 185 ms 9552 KB Output is correct
5 Correct 167 ms 9564 KB Output is correct
6 Correct 179 ms 9584 KB Output is correct
7 Correct 166 ms 9540 KB Output is correct
8 Correct 183 ms 9648 KB Output is correct
9 Correct 175 ms 9576 KB Output is correct
10 Correct 175 ms 9612 KB Output is correct
11 Correct 189 ms 8924 KB Output is correct
12 Correct 214 ms 9080 KB Output is correct
13 Correct 176 ms 9192 KB Output is correct
14 Incorrect 186 ms 9164 KB Output is incorrect: {s, t} is wrong.

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1284 KB Output is correct
2 Correct 31 ms 2204 KB Output is correct
3 Correct 43 ms 3252 KB Output is correct
4 Correct 135 ms 8920 KB Output is correct
5 Correct 142 ms 8904 KB Output is correct
6 Correct 122 ms 9052 KB Output is correct
7 Correct 149 ms 9160 KB Output is correct
8 Correct 126 ms 8924 KB Output is correct
9 Correct 123 ms 9040 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 23 ms 1272 KB Output is correct
3 Correct 135 ms 7624 KB Output is correct
4 Correct 170 ms 9608 KB Output is correct
5 Correct 189 ms 9620 KB Output is correct
6 Correct 168 ms 9560 KB Output is correct
7 Correct 178 ms 9648 KB Output is correct
8 Correct 178 ms 9636 KB Output is correct
9 Incorrect 190 ms 9488 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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