제출 #132728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132728		dvdg6566	통행료 (IOI18_highway)	C++14	0 / 100	23 ms	3644 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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;

void 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);
  }
  ll 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';
  	ll l = ask(q);
  	// cout<<l<<' '<<len<<'\n';
  	if ((ll)len*(ll)B == (ll)l*(ll)A){
  		answer(0,i);
  		return;
  	}
  }
}

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