oj.uz

답안 #1058353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058353 2024-08-14T09:31:55 Z ReLice 통행료 (IOI18_highway) C++17
90 / 100
 152 ms 28652 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define pf push_front
#define sz size()
#define bc back()
#define pob pop_back()
#define pof pop_front()
#define fr first
#define sc second
using namespace std;
const ll N=2e5+7;
const ll inf=1e18;
vector<vector<array<ll,2>>> g(N), g2(N);
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	ll M = V.sz;
	ll s, t, rt;
	ll n = N;
	vll v, u;
	ll i;
	
	for(auto i : V) v.pb(i);
	for(auto i : U) u.pb(i);
	
	vector<int> w(M, 0);
	
	ll x = ask(w);
	
	for(i=0;i<M;i++){
		g[v[i]].pb({u[i], i});
		g[u[i]].pb({v[i], i});
	}
	
	{//getting vertex on the path
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 0);
			
			for(i=0;i<m;i++){
				for(auto [to, r] : g[i]) w[r] = 1;
			}
			
			ll y = ask(w);
			
			if(y == x) l = m;
			else r = m;
		}
		
		rt = r - 1;
	}
	
	vll p(n), d(n);
	vll pr(n), tour;
	vector<vll> dd(n);
	
	auto bfs = [&](ll s){
		for(i=0;i<n;i++){
			dd[i].clear();
			d[i] = inf;
			pr[i] = p[i] = -1;
		}
		
		queue<ll> q;
		q.push(s);
		d[s] = 0;
		
		while(q.size()){
			ll x = q.front();
			q.pop();
			
			dd[d[x]].pb(x);
			
			for(auto [to, r] : g[x]){
				if(d[to] > d[x] + 1){
					d[to] = d[x] + 1 ;
					pr[to] = r;
					p[to] = x;
					q.push(to);
				}
			}
		}
		
		tour.clear();
		for(i=0;i<n;i++){
			for(auto j : dd[i]) tour.pb(j);
		}
	};
	
	vll path;
	auto calc = [&](ll n){
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 1);
			
			for(auto i : path) w[i] =0;
			
			//~ cout<<m<<endl;
			for(i=1;i<m;i++) {
				w[pr[tour[i]]] = 0;
				//~ cout<<v[pr[tour[i]]]<<' '<<u[pr[tour[i]]]<<endl;
			}
			
			ll y = ask(w);
				
			if(x == y) r = m;
			else l = m;
		}
		
		return r - 1;
	};
	
	bfs(rt);
	
	ll l = 1, r = n - 1;
	ll ans;
	
	while ( l <= r ){
		int m = (l + r) / 2;
		
		if ( r - l > 60000 ) m = 60000;
		
		w.assign(M, 1);
		
		for ( int i = 1; i <= m; i++ ){
			w[pr[tour[i]]] = 0;
		}
		
		if ( ask(w) == x ){
			ans = m;
			r = m - 1;
		} else l = m + 1;
	}
	
	s = tour[ans];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	l = 0, r = ans - 1;
	
	while ( l <= r ){
		int m = (l + r) / 2;
		
		w.assign(M, 1);
		
		for ( auto &j: path ) w[j] = 0;
		
		for ( int i = 0; i < m; i++ ){
			w[pr[tour[i + 1]]] = 0;
		}
		
		if ( ask(w) == x ){
			ans = m;
			r = m - 1;
		} else l = m + 1;
	}
	
	t = tour[ans];
	
	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:7: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
   96 |  auto calc = [&](ll n){
      |       ^~~~
highway.cpp:144:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |  s = tour[ans];
      |              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 9 ms 11448 KB Output is correct
3 Correct 106 ms 24044 KB Output is correct
4 Correct 81 ms 24276 KB Output is correct
5 Correct 94 ms 24048 KB Output is correct
6 Correct 104 ms 24024 KB Output is correct
7 Correct 76 ms 24044 KB Output is correct
8 Correct 83 ms 24248 KB Output is correct
9 Correct 72 ms 24232 KB Output is correct
10 Correct 96 ms 24256 KB Output is correct
11 Correct 81 ms 24280 KB Output is correct
12 Correct 102 ms 24536 KB Output is correct
13 Correct 77 ms 24508 KB Output is correct
14 Correct 92 ms 24340 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11620 KB Output is correct
2 Correct 16 ms 13376 KB Output is correct
3 Correct 24 ms 14924 KB Output is correct
4 Correct 70 ms 24588 KB Output is correct
5 Correct 65 ms 24532 KB Output is correct
6 Correct 72 ms 25656 KB Output is correct
7 Correct 70 ms 25588 KB Output is correct
8 Correct 63 ms 24816 KB Output is correct
9 Correct 77 ms 24860 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 12 ms 11352 KB Output is correct
3 Correct 61 ms 21404 KB Output is correct
4 Correct 77 ms 24112 KB Output is correct
5 Correct 64 ms 24040 KB Output is correct
6 Correct 76 ms 24172 KB Output is correct
7 Correct 71 ms 24136 KB Output is correct
8 Correct 72 ms 23972 KB Output is correct
9 Correct 87 ms 24176 KB Output is correct
10 Correct 77 ms 24020 KB Output is correct
11 Correct 95 ms 24500 KB Output is correct
12 Correct 92 ms 24444 KB Output is correct
13 Correct 102 ms 24516 KB Output is correct
14 Correct 100 ms 24476 KB Output is correct
15 Correct 67 ms 24084 KB Output is correct
16 Correct 81 ms 24128 KB Output is correct
17 Correct 109 ms 24552 KB Output is correct
18 Correct 85 ms 24548 KB Output is correct
19 Correct 76 ms 24168 KB Output is correct
20 Correct 78 ms 24628 KB Output is correct
21 Correct 74 ms 24832 KB Output is correct
22 Correct 78 ms 24656 KB Output is correct
23 Correct 73 ms 24532 KB Output is correct
24 Correct 79 ms 24796 KB Output is correct
25 Correct 92 ms 26308 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11608 KB Output is correct
2 Correct 10 ms 11604 KB Output is correct
3 Correct 94 ms 25420 KB Output is correct
4 Correct 98 ms 26320 KB Output is correct
5 Correct 116 ms 28300 KB Output is correct
6 Correct 115 ms 28152 KB Output is correct
7 Correct 119 ms 28144 KB Output is correct
8 Correct 136 ms 28212 KB Output is correct
9 Correct 97 ms 21964 KB Output is correct
10 Correct 97 ms 22812 KB Output is correct
11 Correct 133 ms 24236 KB Output is correct
12 Correct 117 ms 26784 KB Output is correct
13 Correct 119 ms 27492 KB Output is correct
14 Correct 112 ms 28152 KB Output is correct
15 Correct 110 ms 28092 KB Output is correct
16 Correct 98 ms 24292 KB Output is correct
17 Correct 88 ms 24612 KB Output is correct
18 Correct 75 ms 24632 KB Output is correct
19 Correct 77 ms 24392 KB Output is correct
20 Correct 90 ms 24632 KB Output is correct
21 Correct 104 ms 28036 KB Output is correct

Subtask #6
21.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11352 KB Output is correct
2 Correct 11 ms 11460 KB Output is correct
3 Correct 86 ms 25180 KB Output is correct
4 Correct 99 ms 25852 KB Output is correct
5 Correct 102 ms 26428 KB Output is correct
6 Correct 106 ms 28140 KB Output is correct
7 Correct 108 ms 25240 KB Output is correct
8 Correct 94 ms 25860 KB Output is correct
9 Correct 99 ms 26456 KB Output is correct
10 Correct 102 ms 28172 KB Output is correct
11 Correct 116 ms 28580 KB Output is correct
12 Correct 111 ms 28140 KB Output is correct
13 Correct 110 ms 24256 KB Output is correct
14 Correct 105 ms 22684 KB Output is correct
15 Correct 111 ms 24444 KB Output is correct
16 Correct 115 ms 23120 KB Output is correct
17 Correct 112 ms 24208 KB Output is correct
18 Correct 99 ms 22696 KB Output is correct
19 Correct 114 ms 26892 KB Output is correct
20 Correct 113 ms 27528 KB Output is correct
21 Correct 125 ms 28192 KB Output is correct
22 Correct 120 ms 28180 KB Output is correct
23 Correct 130 ms 28652 KB Output is correct
24 Correct 111 ms 28104 KB Output is correct
25 Correct 152 ms 28144 KB Output is correct
26 Correct 117 ms 28112 KB Output is correct
27 Correct 84 ms 24456 KB Output is correct
28 Correct 80 ms 24260 KB Output is correct
29 Correct 77 ms 24868 KB Output is correct
30 Correct 87 ms 24424 KB Output is correct
31 Partially correct 95 ms 24744 KB Output is partially correct
32 Correct 84 ms 24276 KB Output is correct
33 Correct 88 ms 25048 KB Output is correct
34 Correct 83 ms 24760 KB Output is correct
35 Correct 79 ms 24632 KB Output is correct
36 Correct 84 ms 24236 KB Output is correct
37 Correct 95 ms 25256 KB Output is correct
38 Partially correct 96 ms 24656 KB Output is partially correct
39 Correct 101 ms 27900 KB Output is correct
40 Correct 136 ms 27844 KB Output is correct
41 Partially correct 134 ms 27980 KB Output is partially correct
42 Correct 136 ms 28060 KB Output is correct