oj.uz

Submission #115013

# Submission time Handle Problem Language Result Execution time Memory
115013 2019-06-04T11:57:31 Z tinjyu Highway Tolls (IOI18_highway) C++14
11 / 100
 214 ms 9656 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];
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;
}
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;
}
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;
}
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;
}
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;
}
int findlength(int x)
{
    int tp=x;
    while(tp!=point)
    {
        sumlength++;
        tp=father[tp][0];
    }
    return 0;
}
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 364 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 3 ms 424 KB Output is correct
7 Correct 2 ms 300 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 2 ms 380 KB Output is correct
12 Correct 2 ms 360 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 17 ms 1400 KB Output is correct
3 Correct 172 ms 9564 KB Output is correct
4 Correct 204 ms 9548 KB Output is correct
5 Correct 162 ms 9552 KB Output is correct
6 Correct 162 ms 9576 KB Output is correct
7 Correct 166 ms 9552 KB Output is correct
8 Correct 179 ms 9552 KB Output is correct
9 Correct 179 ms 9564 KB Output is correct
10 Correct 201 ms 9552 KB Output is correct
11 Correct 214 ms 8932 KB Output is correct
12 Correct 172 ms 9136 KB Output is correct
13 Correct 175 ms 9208 KB Output is correct
14 Incorrect 194 ms 9248 KB Output is incorrect: {s, t} is wrong.

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1348 KB Output is correct
2 Correct 33 ms 2208 KB Output is correct
3 Correct 53 ms 3212 KB Output is correct
4 Correct 172 ms 8972 KB Output is correct
5 Correct 159 ms 8896 KB Output is correct
6 Correct 145 ms 9064 KB Output is correct
7 Correct 151 ms 9156 KB Output is correct
8 Correct 138 ms 9016 KB Output is correct
9 Correct 147 ms 8964 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 21 ms 1340 KB Output is correct
3 Correct 113 ms 7544 KB Output is correct
4 Correct 159 ms 9656 KB Output is correct
5 Correct 171 ms 9568 KB Output is correct
6 Correct 175 ms 9620 KB Output is correct
7 Correct 186 ms 9572 KB Output is correct
8 Correct 162 ms 9560 KB Output is correct
9 Incorrect 188 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 21 ms 1476 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 27 ms 1452 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -