제출 #293622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293622		Gurban	통행료 (IOI18_highway)	C++17	0 / 100	355 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define mkp make_pair
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int dis[maxn];
vi col;
vector<pii> E[maxn],v;

void st(int nd,int pr){
	if(nd) dis[nd]=dis[pr]+1;
	v.pb({dis[nd],nd});
	for(auto i : E[nd]){
		if(i.ff != pr){
			st(i.ff,nd);
		}
	}
}

bool dfs(int nd,int pr,int pos){
	if(nd==pos) return 1;
	for(auto i : E[nd]){
		if(i.ff != pr){
			if(dfs(i.ff,nd,pos)){
				col[i.ss]=1; 
				return 1;	
			}
			else col[i.ss]=0;
		}
	}
	return 0;
}

void find_pair(int N, vi U, vi V, int A, int B) {
	int M = sz(U);
	// if(M != N-1){
	// 	answer(rand()%N,rand()%N);
	// 	return;	
	// }
	for(int i = 0;i < M;i++){
		E[U[i]].pb({V[i],i});
		E[V[i]].pb({U[i],i});
	}
	col.resize(M);
	int ans = 0;
	st(0,-1);
	sort(all(v));
	for(int i = 0;i < sz(v);i++){
		for(int j = 0;j < sz(col);j++) col[j]=0;
		dfs(0,-1,v[i].ss);
		if(ask(col) == v[i].ff*B) ans=i;
	}
	// cout<<ans<<'\n';
	answer(0, ans);

}

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