제출 #596162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596162		FatihSolak	통행료 (IOI18_highway)	C++17	5 / 100	143 ms	8660 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<pair<int,int>> adj[N];
int par[N];
int paredge[N];
vector<int> x;
void dfs(int v,int pr,int predge,int dep){
	par[v] = pr;
	paredge[v] = predge;
	if(dep == 0){
		x.push_back(v);
		return;
	}
	for(auto u:adj[v]){
		if(u.first == pr)continue;
		dfs(u.first,v,u.second,dep-1);
	}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = u.size();
	for(int i = 0;i<m;i++){
		adj[u[i]].push_back({v[i],i});
		adj[v[i]].push_back({u[i],i});
	}
	vector<int> w(m,0);
	int dep = ask(w) / a;
	dfs(0,-1,-1,dep);
	while(x.size() > 1){
		vector<int> tmp;
		while(tmp.size() < x.size()){
			tmp.push_back(x.back());
			x.pop_back();
		}
		w.assign(m,0);
		for(auto u:tmp){
			w[paredge[u]] = 1;
		}
		if(ask(w) != dep * a){
			x = tmp;
		}
	}
	answer(0, x[0]);
}

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