답안 #1112341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112341	2024-11-14T05:30:40 Z	thelegendary08	통행료 (IOI18_highway)	C++14	18 / 100	106 ms	8876 KB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define pb push_back
#define vvi vector<vector<int>>
#define ll long long int
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pii pair<int,int>
using namespace std;
ll base;
ll len;
int a;
int b;
int m;
pii search(int l, int r){
	if(l == r)return{l, l};
	vi w(m,0);
	int mid = (l + r)/2;
	for(int i = l; i<=mid; i++)w[i] = 1;
	ll ret = ask(w);
	if(ret == base){
		return search(mid + 1, r);
	}
	else if(ret == len * b){
		return search(l, mid);
	}
	else{
		int cnt = (ret - base) / (b - a);
		return {mid - cnt+1, mid - cnt + len};
	}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	bool s3 = true;
	f0r(i, m){
		if(U[i] != i || V[i] != i+1)s3 = false;
	}
	a = A;
	b = B;
	ll ret;
	vi w(m,0);
	ret = ask(w);
	base = ret;
	len = ret/A;
	if(s3){
		pii ans = search(0, m-1);
		answer(ans.first, ans.second + 1);
	}
	else{
		vi dep(N);
		dep[0] = 0;
		queue<int>q;
		q.push(0);
		vb vis(N);
		vis[0] = 1;
		vpii adj[N];
		f0r(i, m){
			adj[U[i]].pb({V[i], i});
			adj[V[i]].pb({U[i], i});
		}
		vi par(N, -1);
		while(!q.empty()){
			int cur = q.front();
			q.pop();
			for(auto u : adj[cur]){
				if(vis[u.first])continue;
				par[u.first] = u.second;
				vis[u.first] = 1;
				dep[u.first] = dep[cur] + 1;
				q.push(u.first);
			}
		}
		//vout(par);
		
		vi poss;
		f0r(i, N){
			if(dep[i] == len)poss.pb(i);
		}
		//vout(poss);
		
		int l = 0;
		int r = poss.size() - 1;
		while(l < r){
			vi w(m, 0);
			int mid = (l + r)/2;
			//set l to mid
			for(int i = l; i<=mid; i++){
				w[par[poss[i]]] = 1;
			}
			ret = ask(w);
			if(ret > base){
				r = mid;
			}
			else{
				l = mid + 1;
			}
		}
	  	answer(0, poss[l]);
	}
	
  	
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	9 ms	1360 KB	Output is correct
3	Correct	92 ms	8800 KB	Output is correct
4	Correct	89 ms	8876 KB	Output is correct
5	Correct	80 ms	8872 KB	Output is correct
6	Correct	91 ms	8776 KB	Output is correct
7	Correct	86 ms	8808 KB	Output is correct
8	Correct	88 ms	8812 KB	Output is correct
9	Correct	91 ms	8708 KB	Output is correct
10	Correct	87 ms	8808 KB	Output is correct
11	Correct	106 ms	8108 KB	Output is correct
12	Correct	83 ms	8040 KB	Output is correct
13	Correct	83 ms	8168 KB	Output is correct
14	Correct	87 ms	8096 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	848 KB	Output is correct
2	Correct	15 ms	848 KB	Output is correct
3	Correct	24 ms	2128 KB	Output is correct
4	Correct	72 ms	2408 KB	Output is correct
5	Correct	68 ms	5212 KB	Output is correct
6	Correct	60 ms	2408 KB	Output is correct
7	Correct	70 ms	5604 KB	Output is correct
8	Correct	64 ms	2380 KB	Output is correct
9	Correct	72 ms	2656 KB	Output is correct