oj.uz

Submission #116508

# Submission time Handle Problem Language Result Execution time Memory
116508 2019-06-12T16:19:13 Z MvC Highway Tolls (IOI18_highway) C++14
51 / 100
 239 ms 13112 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "highway.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,x,y,viz[nmax],l,r,mid,ub,lb;
ll d,d1,f,s;
vector<pair<int,int> >ord,a[nmax],nw;
vector<int>vc;
void dfs(int x,int y)
{
	if(viz[x])return;
	if(y!=-1)ord.pb(mkp(x,y));
	viz[x]=1;
	for(int i=0;i<a[x].size();i++)dfs(a[x][i].fr,a[x][i].sc);
}
void dfs1(int x,int l,int y)
{
	if(viz[x])return;
	viz[x]=1;
	if(l==d/f)nw.pb(mkp(x,y));
	for(int i=0;i<a[x].size();i++)dfs1(a[x][i].fr,l+1,a[x][i].sc);
}
/*int ask()
{
	ll x;
	for(int i=0;i<n-1;i++)cout<<vc[i]<<" ";
	cout<<endl;
	cin>>x;
	return x;
}*/
int ok(int x)
{
	int i;
	for(i=0;i<x;i++)vc[ord[i].sc]=1;
	for(;i<n-1;i++)vc[ord[i].sc]=0;
	return (ask(vc)<d1);
}
int ok1(int x)
{
	int i;
	for(i=0;i<n-1;i++)vc[i]=0;
	for(i=0;i<x;i++)vc[nw[i].sc]=1;
	return (ask(vc)==d);
}
void find_pair(int N,vector<int>U,vector<int>V,int A,int B)
{
	n=N;
	for(i=0;i<n-1;i++)
	{
		x=U[i],y=V[i];
		a[x].pb(mkp(y,i));
		a[y].pb(mkp(x,i));
	}
	f=A,s=B;
	dfs(1,-1);
	for(i=0;i<n-1;i++)vc.pb(0);
	d=ask(vc);
	d1=(d/f)*s;
	l=1,r=n-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok(mid))l=mid+1;
		else ub=mid,r=mid-1;
	}
	memset(viz,0,sizeof(viz));
	dfs1(ord[ub-1].fr,0,-1);
	l=1,r=(int)nw.size();
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok1(mid))l=mid+1;
		else lb=mid,r=mid-1;
	}
	answer(nw[lb-1].fr,ord[ub-1].fr);
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].pb(mkp(y,i-1));
		a[y].pb(mkp(x,i-1));
	}
	cin>>f>>s;
	dfs(1,-1);
	cout<<endl;
	//for(i=0;i<n-1;i++)cout<<ord[i].fr<<" "<<ord[i].sc<<endl;
	for(i=0;i<n-1;i++)vc.pb(0);
	d=ask();
	d1=(d/f)*s;
	l=1,r=n-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok(mid))l=mid+1;
		else ub=mid,r=mid-1;
	}
	memset(viz,0,sizeof(viz));
	dfs1(ord[ub-1].fr,0,-1);
	//for(i=0;i<nw.size();i++)cout<<nw[i].fr<<" "<<nw[i].sc<<endl;
	l=1,r=(int)nw.size();
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok1(mid))l=mid+1;
		else lb=mid,r=mid-1;
	}
	//cout<<lb<<" "<<ub<<endl;
	cout<<nw[lb-1].fr<<" "<<ord[ub-1].fr<<endl;
    return 0;
}*/
/*
9
1 2
2 3
2 4
1 6
1 5
8 9
6 7
6 8
2 5
*/

Compilation message

highway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
highway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
highway.cpp: In function 'void dfs(int, int)':
highway.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)dfs(a[x][i].fr,a[x][i].sc);
              ~^~~~~~~~~~~~
highway.cpp: In function 'void dfs1(int, int, int)':
highway.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)dfs1(a[x][i].fr,l+1,a[x][i].sc);
              ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3024 KB Output is correct
2 Correct 5 ms 2940 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 5 ms 3024 KB Output is correct
5 Correct 5 ms 2984 KB Output is correct
6 Correct 4 ms 3024 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 5 ms 3016 KB Output is correct
11 Correct 4 ms 2940 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3000 KB Output is correct
2 Correct 46 ms 3704 KB Output is correct
3 Correct 205 ms 9440 KB Output is correct
4 Correct 180 ms 9460 KB Output is correct
5 Correct 204 ms 9428 KB Output is correct
6 Correct 238 ms 9428 KB Output is correct
7 Correct 202 ms 9424 KB Output is correct
8 Correct 224 ms 9432 KB Output is correct
9 Correct 217 ms 9492 KB Output is correct
10 Correct 211 ms 9472 KB Output is correct
11 Correct 232 ms 10004 KB Output is correct
12 Correct 188 ms 10348 KB Output is correct
13 Correct 198 ms 10044 KB Output is correct
14 Correct 225 ms 9952 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4136 KB Output is correct
2 Correct 36 ms 5272 KB Output is correct
3 Correct 58 ms 6392 KB Output is correct
4 Correct 153 ms 13068 KB Output is correct
5 Correct 173 ms 13100 KB Output is correct
6 Correct 164 ms 13076 KB Output is correct
7 Correct 166 ms 13112 KB Output is correct
8 Correct 154 ms 13084 KB Output is correct
9 Correct 134 ms 13072 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3032 KB Output is correct
2 Correct 28 ms 3704 KB Output is correct
3 Correct 157 ms 8144 KB Output is correct
4 Correct 210 ms 9504 KB Output is correct
5 Correct 194 ms 9432 KB Output is correct
6 Correct 185 ms 9504 KB Output is correct
7 Correct 188 ms 9432 KB Output is correct
8 Correct 173 ms 9400 KB Output is correct
9 Correct 188 ms 9436 KB Output is correct
10 Correct 234 ms 9512 KB Output is correct
11 Correct 231 ms 9612 KB Output is correct
12 Correct 213 ms 10260 KB Output is correct
13 Correct 217 ms 9876 KB Output is correct
14 Correct 239 ms 10384 KB Output is correct
15 Correct 215 ms 9416 KB Output is correct
16 Correct 192 ms 9416 KB Output is correct
17 Correct 191 ms 9816 KB Output is correct
18 Correct 192 ms 10168 KB Output is correct
19 Correct 186 ms 9432 KB Output is correct
20 Correct 208 ms 10704 KB Output is correct
21 Correct 179 ms 11084 KB Output is correct
22 Correct 176 ms 11084 KB Output is correct
23 Correct 188 ms 10348 KB Output is correct
24 Correct 173 ms 10564 KB Output is correct
25 Correct 206 ms 12720 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3392 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3448 KB Incorrect
2 Halted 0 ms 0 KB -