oj.uz

답안 #1032783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032783 2024-07-24T08:34:03 Z AmirAli_H1 통행료 (IOI18_highway) C++17
90 / 100
 185 ms 15596 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int oo = 1e9 + 7;

int n, m; ll D;
vector<int> adj[maxn], ls;
vector<pii> E; bool M[maxn];
int arr[maxn], dis[maxn];
queue<int> qu;

void bfs(int v) {
	fill(dis, dis + n, oo);
	dis[v] = 0; qu.push(v);
	while (!qu.empty()) {
		v = qu.front(); qu.pop();
		for (int u : adj[v]) {
			if (dis[v] + 1 < dis[u]) {
				dis[u] = dis[v] + 1;
				qu.push(u);
			}
		}
	}
}

bool cmp(int i, int j) {
	return (dis[i] < dis[j]);
}

ll askx() {
	ls.clear(); ls.resize(m);
	for (int i = 0; i < m; i++) {
		int u = E[i].F, v = E[i].S;
		if (M[u] || M[v]) ls[i] = 1;
		else ls[i] = 0;
	}
	return ask(ls);
}

int getv(vector<int> vc) {
	if (len(vc) == 1) return vc[0];
	
	vector<int> vc1, vc2;
	int mid = (len(vc) / 2);
	for (int i = 0; i < mid; i++) vc1.pb(vc[i]);
	for (int i = mid; i < len(vc); i++) vc2.pb(vc[i]);
	
	for (int u : vc1) M[u] = 1;
	if (askx() == D) return getv(vc2);
	else {
		for (int u : vc1) M[u] = 0;
		return getv(vc1);
	}
}

int getx(int R) {
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	int l = 0, r = n;
	if (R != -1) {
		l = n; r = 0;
		for (int i = 0; i < n; i++) {
			if (dis[arr[i]] == R) {
				l = min(l, i); r = max(r, i + 1);
			}
		}
	}
	
	while (r - l > 1) {
		int mid = (l + r) / 2;
		for (int j = 0; j < n; j++) {
			M[arr[j]] = (j >= mid);
		}
		if (askx() > D) l = mid;
		else r = mid;
	}
	return arr[l];
}

void find_pair(int Nx, vector<int> ux, vector<int> vx, int A, int B) {
	n = Nx; m = len(ux);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
		E.pb(Mp(u, v));
	}
	D = askx();
	
	vector<int> vc;
	for (int i = 0; i < n; i++) {
		M[i] = 0; vc.pb(i);
	}
	int vr = getv(vc);
	
	bfs(vr); int u1 = getx(-1);
	bfs(u1); int u2 = getx(D / A);
	answer(u1, u2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 10 ms 7512 KB Output is correct
3 Correct 103 ms 14144 KB Output is correct
4 Correct 92 ms 14152 KB Output is correct
5 Correct 100 ms 14140 KB Output is correct
6 Correct 94 ms 14148 KB Output is correct
7 Correct 96 ms 14152 KB Output is correct
8 Correct 91 ms 14144 KB Output is correct
9 Correct 95 ms 14144 KB Output is correct
10 Correct 103 ms 14144 KB Output is correct
11 Correct 88 ms 14048 KB Output is correct
12 Correct 96 ms 14056 KB Output is correct
13 Correct 99 ms 14224 KB Output is correct
14 Correct 84 ms 14036 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7512 KB Output is correct
2 Correct 15 ms 8452 KB Output is correct
3 Correct 23 ms 9128 KB Output is correct
4 Correct 82 ms 14292 KB Output is correct
5 Correct 80 ms 14068 KB Output is correct
6 Correct 77 ms 14140 KB Output is correct
7 Correct 66 ms 14060 KB Output is correct
8 Correct 88 ms 14048 KB Output is correct
9 Correct 79 ms 14132 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 12 ms 7512 KB Output is correct
3 Correct 73 ms 12572 KB Output is correct
4 Correct 118 ms 14136 KB Output is correct
5 Correct 89 ms 14160 KB Output is correct
6 Correct 103 ms 14152 KB Output is correct
7 Correct 96 ms 14168 KB Output is correct
8 Correct 89 ms 14144 KB Output is correct
9 Correct 110 ms 14148 KB Output is correct
10 Correct 119 ms 14140 KB Output is correct
11 Correct 120 ms 14052 KB Output is correct
12 Correct 97 ms 14112 KB Output is correct
13 Correct 122 ms 14040 KB Output is correct
14 Correct 113 ms 14060 KB Output is correct
15 Correct 82 ms 14144 KB Output is correct
16 Correct 98 ms 14144 KB Output is correct
17 Correct 109 ms 14044 KB Output is correct
18 Correct 106 ms 14036 KB Output is correct
19 Correct 96 ms 14156 KB Output is correct
20 Correct 117 ms 14056 KB Output is correct
21 Correct 125 ms 14400 KB Output is correct
22 Correct 126 ms 14392 KB Output is correct
23 Correct 116 ms 14592 KB Output is correct
24 Correct 106 ms 14360 KB Output is correct
25 Correct 112 ms 14404 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 7512 KB Output is correct
2 Correct 13 ms 7512 KB Output is correct
3 Correct 122 ms 14456 KB Output is correct
4 Correct 137 ms 14760 KB Output is correct
5 Correct 152 ms 15432 KB Output is correct
6 Correct 155 ms 15432 KB Output is correct
7 Correct 185 ms 15404 KB Output is correct
8 Correct 143 ms 15416 KB Output is correct
9 Correct 137 ms 12596 KB Output is correct
10 Correct 127 ms 13284 KB Output is correct
11 Correct 157 ms 13416 KB Output is correct
12 Correct 167 ms 14708 KB Output is correct
13 Correct 150 ms 14996 KB Output is correct
14 Correct 147 ms 15296 KB Output is correct
15 Correct 176 ms 15284 KB Output is correct
16 Correct 128 ms 13604 KB Output is correct
17 Correct 118 ms 14500 KB Output is correct
18 Correct 106 ms 14604 KB Output is correct
19 Correct 115 ms 14808 KB Output is correct
20 Correct 110 ms 14616 KB Output is correct
21 Correct 118 ms 15388 KB Output is correct

Subtask #6
21.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 7608 KB Output is correct
2 Correct 10 ms 7636 KB Output is correct
3 Correct 126 ms 14480 KB Output is correct
4 Correct 126 ms 14700 KB Output is correct
5 Correct 150 ms 14816 KB Output is correct
6 Correct 142 ms 15428 KB Output is correct
7 Correct 100 ms 14496 KB Output is correct
8 Correct 130 ms 14768 KB Output is correct
9 Correct 139 ms 14760 KB Output is correct
10 Correct 145 ms 15432 KB Output is correct
11 Correct 171 ms 15440 KB Output is correct
12 Correct 183 ms 15596 KB Output is correct
13 Correct 129 ms 13280 KB Output is correct
14 Correct 116 ms 12956 KB Output is correct
15 Correct 159 ms 13252 KB Output is correct
16 Correct 148 ms 13036 KB Output is correct
17 Correct 167 ms 13284 KB Output is correct
18 Correct 137 ms 13144 KB Output is correct
19 Correct 155 ms 14672 KB Output is correct
20 Correct 132 ms 14900 KB Output is correct
21 Correct 161 ms 15296 KB Output is correct
22 Correct 159 ms 15468 KB Output is correct
23 Correct 143 ms 15304 KB Output is correct
24 Correct 155 ms 15288 KB Output is correct
25 Correct 182 ms 15268 KB Output is correct
26 Correct 152 ms 15516 KB Output is correct
27 Correct 113 ms 14572 KB Output is correct
28 Partially correct 115 ms 14520 KB Output is partially correct
29 Partially correct 110 ms 14656 KB Output is partially correct
30 Partially correct 114 ms 14864 KB Output is partially correct
31 Correct 124 ms 14532 KB Output is correct
32 Partially correct 134 ms 15068 KB Output is partially correct
33 Correct 113 ms 14888 KB Output is correct
34 Correct 107 ms 14752 KB Output is correct
35 Partially correct 101 ms 14528 KB Output is partially correct
36 Partially correct 123 ms 14456 KB Output is partially correct
37 Correct 120 ms 14716 KB Output is correct
38 Correct 138 ms 14624 KB Output is correct
39 Correct 140 ms 15368 KB Output is correct
40 Correct 140 ms 15404 KB Output is correct
41 Correct 154 ms 15364 KB Output is correct
42 Correct 137 ms 15376 KB Output is correct