oj.uz

답안 #1064011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064011 2024-08-18T07:52:50 Z Tob 통행료 (IOI18_highway) C++14
100 / 100
 178 ms 15324 KB 
#include <bits/stdc++.h>

#include "highway.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int maxN = 90007;

ll odis;
int bio[maxN], dub[maxN], col[maxN];
vector <pii> adj[maxN];

void dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y.F]) continue;
		dub[y.F] = dub[x]+1;
		dfs(y.F);
	}
}

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
	int m = u.size();
	vector <int> tmp(m, 0);
	odis = ask(tmp);
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	dfs(0);
	
	vector <int> e;
	for (int i = 0; i < m; i++) e.pb(i);
	
	sort(all(e), [&](int x, int y) {return max(dub[u[x]], dub[v[x]]) > max(dub[u[y]], dub[v[y]]);});
	int lo = 0, hi = m-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		vector <int> ed(m, 0);
		for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
		if (odis != ask(ed)) hi = mid;
		else lo = mid+1;
	}
	
	int nx = u[e[lo]], ny = v[e[lo]];
	queue <int> q;
	memset(bio, -1, sizeof bio);
	bio[nx] = 0; bio[ny] = 0; col[ny] = 1;
	q.push(nx); q.push(ny);
	vector <pii> dod[2];
	dod[0].pb({nx, e[lo]});
	dod[1].pb({ny, e[lo]});
	tmp[e[lo]] = 1;
	
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (auto y : adj[x]) {
			if (bio[y.F] != -1) continue;
			bio[y.F] = bio[x] + 1;
			dod[col[x]].pb(y);
			col[y.F] = col[x];
			tmp[y.S] = 1;
			q.push(y.F);
		}
	}
	reverse(all(dod[0])); reverse(all(dod[1]));
	auto check = [&](int o) {
		lo = 0, hi = dod[o].size()-1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			vector <int> ed(m, 0);
			for (int i = 0; i <= mid; i++) ed[dod[o][i].S] = 1;
			for (int i = 0; i < m; i++) if (!tmp[i]) ed[i] = 1;
			if (odis != ask(ed)) hi = mid;
			else lo = mid+1;
		}
		return dod[o][lo].F;
	};
	
	int x = check(0), y = check(1);
	answer(x, y);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2904 KB Output is correct
2 Correct 11 ms 3672 KB Output is correct
3 Correct 109 ms 10480 KB Output is correct
4 Correct 97 ms 10516 KB Output is correct
5 Correct 98 ms 10556 KB Output is correct
6 Correct 91 ms 10624 KB Output is correct
7 Correct 97 ms 10640 KB Output is correct
8 Correct 96 ms 10808 KB Output is correct
9 Correct 94 ms 10624 KB Output is correct
10 Correct 97 ms 10588 KB Output is correct
11 Correct 121 ms 10860 KB Output is correct
12 Correct 117 ms 11504 KB Output is correct
13 Correct 106 ms 11012 KB Output is correct
14 Correct 105 ms 10588 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4184 KB Output is correct
2 Correct 19 ms 5392 KB Output is correct
3 Correct 25 ms 6648 KB Output is correct
4 Correct 78 ms 14420 KB Output is correct
5 Correct 89 ms 13896 KB Output is correct
6 Correct 77 ms 14116 KB Output is correct
7 Correct 77 ms 14164 KB Output is correct
8 Correct 69 ms 14072 KB Output is correct
9 Correct 77 ms 14484 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 10 ms 3848 KB Output is correct
3 Correct 71 ms 8844 KB Output is correct
4 Correct 91 ms 10424 KB Output is correct
5 Correct 91 ms 10576 KB Output is correct
6 Correct 91 ms 10540 KB Output is correct
7 Correct 88 ms 10612 KB Output is correct
8 Correct 91 ms 10500 KB Output is correct
9 Correct 96 ms 10620 KB Output is correct
10 Correct 93 ms 10516 KB Output is correct
11 Correct 108 ms 10584 KB Output is correct
12 Correct 106 ms 11540 KB Output is correct
13 Correct 104 ms 11216 KB Output is correct
14 Correct 111 ms 11640 KB Output is correct
15 Correct 87 ms 10596 KB Output is correct
16 Correct 90 ms 10608 KB Output is correct
17 Correct 107 ms 11152 KB Output is correct
18 Correct 111 ms 11056 KB Output is correct
19 Correct 95 ms 10592 KB Output is correct
20 Correct 101 ms 11872 KB Output is correct
21 Correct 69 ms 11240 KB Output is correct
22 Correct 81 ms 11732 KB Output is correct
23 Correct 81 ms 10772 KB Output is correct
24 Correct 81 ms 11116 KB Output is correct
25 Correct 98 ms 13740 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 3960 KB Output is correct
2 Correct 15 ms 3880 KB Output is correct
3 Correct 125 ms 11740 KB Output is correct
4 Correct 135 ms 12688 KB Output is correct
5 Correct 178 ms 14596 KB Output is correct
6 Correct 161 ms 14208 KB Output is correct
7 Correct 167 ms 14276 KB Output is correct
8 Correct 172 ms 14476 KB Output is correct
9 Correct 103 ms 10088 KB Output is correct
10 Correct 96 ms 10580 KB Output is correct
11 Correct 132 ms 10732 KB Output is correct
12 Correct 169 ms 13748 KB Output is correct
13 Correct 162 ms 14056 KB Output is correct
14 Correct 165 ms 15324 KB Output is correct
15 Correct 170 ms 15112 KB Output is correct
16 Correct 146 ms 12624 KB Output is correct
17 Correct 94 ms 11060 KB Output is correct
18 Correct 83 ms 11032 KB Output is correct
19 Correct 87 ms 10952 KB Output is correct
20 Correct 91 ms 10936 KB Output is correct
21 Correct 161 ms 14068 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3672 KB Output is correct
2 Correct 12 ms 3912 KB Output is correct
3 Correct 110 ms 11724 KB Output is correct
4 Correct 126 ms 12228 KB Output is correct
5 Correct 146 ms 13156 KB Output is correct
6 Correct 165 ms 14328 KB Output is correct
7 Correct 125 ms 11996 KB Output is correct
8 Correct 126 ms 12208 KB Output is correct
9 Correct 139 ms 12816 KB Output is correct
10 Correct 169 ms 14208 KB Output is correct
11 Correct 171 ms 14336 KB Output is correct
12 Correct 173 ms 14156 KB Output is correct
13 Correct 130 ms 10724 KB Output is correct
14 Correct 121 ms 10700 KB Output is correct
15 Correct 110 ms 10732 KB Output is correct
16 Correct 102 ms 10580 KB Output is correct
17 Correct 108 ms 10728 KB Output is correct
18 Correct 112 ms 10720 KB Output is correct
19 Correct 166 ms 14472 KB Output is correct
20 Correct 172 ms 14760 KB Output is correct
21 Correct 177 ms 15272 KB Output is correct
22 Correct 173 ms 15168 KB Output is correct
23 Correct 155 ms 15100 KB Output is correct
24 Correct 160 ms 15104 KB Output is correct
25 Correct 178 ms 14984 KB Output is correct
26 Correct 169 ms 15140 KB Output is correct
27 Correct 84 ms 10880 KB Output is correct
28 Correct 77 ms 10804 KB Output is correct
29 Correct 91 ms 11032 KB Output is correct
30 Correct 90 ms 10892 KB Output is correct
31 Correct 108 ms 10828 KB Output is correct
32 Correct 90 ms 10744 KB Output is correct
33 Correct 108 ms 11012 KB Output is correct
34 Correct 85 ms 10856 KB Output is correct
35 Correct 88 ms 10884 KB Output is correct
36 Correct 83 ms 10776 KB Output is correct
37 Correct 102 ms 10956 KB Output is correct
38 Correct 96 ms 10964 KB Output is correct
39 Correct 174 ms 13892 KB Output is correct
40 Correct 159 ms 14164 KB Output is correct
41 Correct 176 ms 13964 KB Output is correct
42 Correct 144 ms 13564 KB Output is correct