oj.uz

Submission #116509

# Submission time Handle Problem Language Result Execution time Memory
116509 2019-06-12T16:20:08 Z MvC Highway Tolls (IOI18_highway) C++14
51 / 100
 243 ms 13124 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 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);
}

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 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 4 ms 3020 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2984 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 5 ms 2944 KB Output is correct
12 Correct 5 ms 2940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 26 ms 3800 KB Output is correct
3 Correct 198 ms 9428 KB Output is correct
4 Correct 203 ms 9436 KB Output is correct
5 Correct 237 ms 9452 KB Output is correct
6 Correct 198 ms 9424 KB Output is correct
7 Correct 169 ms 9420 KB Output is correct
8 Correct 209 ms 9508 KB Output is correct
9 Correct 214 ms 9428 KB Output is correct
10 Correct 243 ms 9452 KB Output is correct
11 Correct 219 ms 10152 KB Output is correct
12 Correct 213 ms 10376 KB Output is correct
13 Correct 208 ms 10120 KB Output is correct
14 Correct 205 ms 10080 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4088 KB Output is correct
2 Correct 40 ms 5256 KB Output is correct
3 Correct 55 ms 6336 KB Output is correct
4 Correct 169 ms 13080 KB Output is correct
5 Correct 168 ms 13068 KB Output is correct
6 Correct 148 ms 13068 KB Output is correct
7 Correct 151 ms 13080 KB Output is correct
8 Correct 145 ms 13124 KB Output is correct
9 Correct 167 ms 13060 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 31 ms 3692 KB Output is correct
3 Correct 157 ms 8084 KB Output is correct
4 Correct 202 ms 9428 KB Output is correct
5 Correct 217 ms 9488 KB Output is correct
6 Correct 194 ms 9448 KB Output is correct
7 Correct 199 ms 9436 KB Output is correct
8 Correct 199 ms 9528 KB Output is correct
9 Correct 211 ms 9420 KB Output is correct
10 Correct 207 ms 9508 KB Output is correct
11 Correct 238 ms 9664 KB Output is correct
12 Correct 227 ms 10268 KB Output is correct
13 Correct 203 ms 9756 KB Output is correct
14 Correct 206 ms 10388 KB Output is correct
15 Correct 195 ms 9404 KB Output is correct
16 Correct 190 ms 9408 KB Output is correct
17 Correct 183 ms 9936 KB Output is correct
18 Correct 213 ms 10252 KB Output is correct
19 Correct 174 ms 9436 KB Output is correct
20 Correct 209 ms 10720 KB Output is correct
21 Correct 167 ms 11088 KB Output is correct
22 Correct 185 ms 11072 KB Output is correct
23 Correct 189 ms 10216 KB Output is correct
24 Correct 177 ms 10564 KB Output is correct
25 Correct 241 ms 12724 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3404 KB Incorrect
2 Halted 0 ms 0 KB -