oj.uz

답안 #1058130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058130 2024-08-14T08:38:25 Z ReLice 통행료 (IOI18_highway) C++17
90 / 100
 138 ms 28432 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 k = calc(n);
	s = tour[k];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	t = tour[calc(k)];
	
	answer(s, t);
}

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 9768 KB Output is correct
4 Correct 3 ms 9816 KB Output is correct
5 Correct 3 ms 9816 KB Output is correct
6 Correct 2 ms 9848 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9808 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 2 ms 9816 KB Output is correct
12 Correct 2 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 10 ms 11508 KB Output is correct
3 Correct 86 ms 24224 KB Output is correct
4 Correct 86 ms 24020 KB Output is correct
5 Correct 99 ms 23988 KB Output is correct
6 Correct 98 ms 24044 KB Output is correct
7 Correct 79 ms 24136 KB Output is correct
8 Correct 85 ms 24252 KB Output is correct
9 Correct 74 ms 24220 KB Output is correct
10 Correct 84 ms 24032 KB Output is correct
11 Correct 88 ms 24256 KB Output is correct
12 Correct 97 ms 24484 KB Output is correct
13 Correct 92 ms 24348 KB Output is correct
14 Correct 93 ms 24508 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11624 KB Output is correct
2 Correct 15 ms 13288 KB Output is correct
3 Correct 23 ms 14920 KB Output is correct
4 Correct 64 ms 24880 KB Output is correct
5 Correct 78 ms 24556 KB Output is correct
6 Correct 65 ms 25356 KB Output is correct
7 Correct 67 ms 25548 KB Output is correct
8 Correct 73 ms 24936 KB Output is correct
9 Correct 64 ms 24852 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 9 ms 11312 KB Output is correct
3 Correct 55 ms 21228 KB Output is correct
4 Correct 92 ms 24084 KB Output is correct
5 Correct 81 ms 24140 KB Output is correct
6 Correct 83 ms 24176 KB Output is correct
7 Correct 92 ms 24124 KB Output is correct
8 Correct 71 ms 24136 KB Output is correct
9 Correct 96 ms 24024 KB Output is correct
10 Correct 88 ms 24264 KB Output is correct
11 Correct 99 ms 24420 KB Output is correct
12 Correct 100 ms 24492 KB Output is correct
13 Correct 94 ms 24476 KB Output is correct
14 Correct 92 ms 24400 KB Output is correct
15 Correct 92 ms 24036 KB Output is correct
16 Correct 95 ms 24064 KB Output is correct
17 Correct 109 ms 24496 KB Output is correct
18 Correct 88 ms 24388 KB Output is correct
19 Correct 81 ms 24156 KB Output is correct
20 Correct 80 ms 24484 KB Output is correct
21 Correct 87 ms 24660 KB Output is correct
22 Correct 90 ms 24660 KB Output is correct
23 Correct 78 ms 24528 KB Output is correct
24 Correct 80 ms 24540 KB Output is correct
25 Correct 103 ms 26244 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11348 KB Output is correct
2 Correct 13 ms 11600 KB Output is correct
3 Correct 86 ms 25416 KB Output is correct
4 Correct 98 ms 26332 KB Output is correct
5 Correct 107 ms 28100 KB Output is correct
6 Correct 114 ms 28432 KB Output is correct
7 Correct 118 ms 28140 KB Output is correct
8 Correct 113 ms 28212 KB Output is correct
9 Correct 112 ms 21948 KB Output is correct
10 Correct 94 ms 22820 KB Output is correct
11 Correct 100 ms 24244 KB Output is correct
12 Correct 115 ms 26784 KB Output is correct
13 Correct 110 ms 27620 KB Output is correct
14 Correct 118 ms 28164 KB Output is correct
15 Correct 112 ms 28092 KB Output is correct
16 Correct 107 ms 24284 KB Output is correct
17 Correct 79 ms 24520 KB Output is correct
18 Correct 104 ms 24632 KB Output is correct
19 Correct 75 ms 24392 KB Output is correct
20 Correct 82 ms 24560 KB Output is correct
21 Correct 106 ms 28036 KB Output is correct

Subtask #6
21.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Correct 12 ms 11652 KB Output is correct
3 Correct 84 ms 25160 KB Output is correct
4 Correct 90 ms 25860 KB Output is correct
5 Correct 109 ms 26444 KB Output is correct
6 Correct 112 ms 28076 KB Output is correct
7 Correct 99 ms 25288 KB Output is correct
8 Correct 99 ms 25888 KB Output is correct
9 Correct 93 ms 26332 KB Output is correct
10 Correct 105 ms 28164 KB Output is correct
11 Correct 115 ms 28144 KB Output is correct
12 Correct 118 ms 28156 KB Output is correct
13 Correct 125 ms 24276 KB Output is correct
14 Correct 89 ms 22944 KB Output is correct
15 Correct 100 ms 24244 KB Output is correct
16 Correct 98 ms 22840 KB Output is correct
17 Correct 100 ms 24208 KB Output is correct
18 Correct 102 ms 22700 KB Output is correct
19 Correct 105 ms 26912 KB Output is correct
20 Correct 104 ms 27520 KB Output is correct
21 Correct 109 ms 28080 KB Output is correct
22 Correct 115 ms 28168 KB Output is correct
23 Correct 128 ms 28184 KB Output is correct
24 Correct 120 ms 28104 KB Output is correct
25 Correct 124 ms 28168 KB Output is correct
26 Correct 104 ms 28108 KB Output is correct
27 Correct 79 ms 24456 KB Output is correct
28 Partially correct 77 ms 24256 KB Output is partially correct
29 Partially correct 80 ms 24864 KB Output is partially correct
30 Correct 79 ms 24420 KB Output is correct
31 Correct 76 ms 24364 KB Output is correct
32 Correct 78 ms 24280 KB Output is correct
33 Correct 77 ms 25052 KB Output is correct
34 Correct 70 ms 24760 KB Output is correct
35 Correct 78 ms 24632 KB Output is correct
36 Correct 74 ms 24224 KB Output is correct
37 Correct 76 ms 24776 KB Output is correct
38 Correct 90 ms 24760 KB Output is correct
39 Correct 113 ms 27928 KB Output is correct
40 Correct 110 ms 27824 KB Output is correct
41 Partially correct 138 ms 28008 KB Output is partially correct
42 Correct 123 ms 28080 KB Output is correct