Submission #132727

#	Time	Username	Problem	Language	Result	Execution time	Memory
132727		dvdg6566	Highway Tolls (IOI18_highway)	C++14	0 / 100	24 ms	3824 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

vpi V[100100];
int sub[100100];
vi q;
pi par[100100];
int rt;
int blk[100100];
int ban[100100];
int ind;

int dfs(int x, int p){
	for (auto v:V[x])if (v.f!=p){
		par[v.f] = mp(x, v.s);
		dfs(v.f,x);
	}
}


void find_pair(int N, std::vector<int> U, std::vector<int> _V, int A, int B) {
  int M = U.size();
  q.resize(N-1,0);
  for (int i=0;i<M;++i){
  	int a=_V[i];
  	int b=U[i];
  	V[a].pb(b,i);
  	V[b].pb(a,i);
  }
  int len=ask(q);
  dfs(0,-1);
  for (int i=1;i<N;++i){
  	for(int j=0;j<N;++j)q[i]=0;
  	int x=i;
  	while(x){
  		q[par[x].s]=1;
  		x=par[x].f;
  	}
  	// for (int i=0;i<N-1;++i)cout<<q[i]<<' ';cout<<'\n';
  	int l = ask(q);
  	// cout<<l<<' '<<len<<'\n';
  	if (len*B == l*A){
  		answer(0,i);
  		return;
  	}
  }
}

Compilation message (stderr)

highway.cpp: In function 'int dfs(int, int)':
highway.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31