oj.uz

답안 #435897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435897 2021-06-23T22:20:08 Z benedict0724 통행료 (IOI18_highway) C++17
100 / 100
 722 ms 11012 KB 
#include "highway.h"
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;

vector<pair<int, int>> adj[90002];
vector<int> w;
int now, M;
int bfsorder[90002];
bool visited[90002];
int dist[90002][3];
ll D;
int K = -1, S = -1, T = -1;

void bfs(int x, int N, int t)
{
    for(int i=0;i<N;i++) visited[i] = false;
    visited[x] = true;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        if(t == 2 && dist[curr][t] == D && dist[curr][1] == D - dist[S][1]) bfsorder[--now] = curr;
        else if(t < 2) bfsorder[--now] = curr;

        for(auto u : adj[curr])
        {
            int i = u.first, j = u.second;
            if(!visited[i])
            {
                visited[i] = true;
                q.push(i);
                dist[i][t] = dist[curr][t] + 1;
            }
        }
    }
}

void makezero()
{
    for(int i=0;i<M;i++) w[i] = 0;
}

void binarysearch(int l, int r, ll zerotoll, int k)
{
    if(l == r)
    {
        if(k == 0) K = bfsorder[l];
        if(k == 1) S = bfsorder[l];
        if(k == 2) T = bfsorder[l];
        return;
    }
    int mid = (l + r)/2;
    makezero();
    for(int i=now;i<=mid;i++)
    {
        for(auto u : adj[bfsorder[i]])
        {
            w[u.second] = 1;
        }
    }
    ll toll = ask(w);

    if(toll > zerotoll) binarysearch(l, mid, zerotoll, k);
    else binarysearch(mid+1, r, zerotoll, k);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    M = U.size();
    for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); }
    w.resize(M);
    makezero();
    ll zerotoll = ask(w);

    D = zerotoll / A;

    now = N; bfs(0, N, 0);
    binarysearch(0, N-1, zerotoll, 0);
    now = N; bfs(K, N, 1);
    binarysearch(0, N-1, zerotoll, 1);
    if(dist[S][1] == D) { answer(K, S); return; }
    now = N; bfs(S, N, 2);
    binarysearch(now, N-1, zerotoll, 2);

    answer(S, T);
}

Compilation message

highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:32:30: warning: unused variable 'j' [-Wunused-variable]
   32 |             int i = u.first, j = u.second;
      |                              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2476 KB Output is correct
2 Correct 25 ms 3144 KB Output is correct
3 Correct 377 ms 9192 KB Output is correct
4 Correct 264 ms 9192 KB Output is correct
5 Correct 394 ms 9172 KB Output is correct
6 Correct 197 ms 9100 KB Output is correct
7 Correct 457 ms 9260 KB Output is correct
8 Correct 556 ms 9180 KB Output is correct
9 Correct 445 ms 9200 KB Output is correct
10 Correct 344 ms 9224 KB Output is correct
11 Correct 405 ms 8496 KB Output is correct
12 Correct 455 ms 8488 KB Output is correct
13 Correct 467 ms 8492 KB Output is correct
14 Correct 409 ms 8484 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3004 KB Output is correct
2 Correct 49 ms 3708 KB Output is correct
3 Correct 61 ms 4400 KB Output is correct
4 Correct 194 ms 8484 KB Output is correct
5 Correct 123 ms 8492 KB Output is correct
6 Correct 202 ms 8484 KB Output is correct
7 Correct 134 ms 8576 KB Output is correct
8 Correct 201 ms 8480 KB Output is correct
9 Correct 224 ms 8484 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2376 KB Output is correct
2 Correct 26 ms 3136 KB Output is correct
3 Correct 233 ms 7616 KB Output is correct
4 Correct 389 ms 9072 KB Output is correct
5 Correct 416 ms 9080 KB Output is correct
6 Correct 277 ms 9088 KB Output is correct
7 Correct 273 ms 9176 KB Output is correct
8 Correct 423 ms 9072 KB Output is correct
9 Correct 279 ms 9092 KB Output is correct
10 Correct 438 ms 9080 KB Output is correct
11 Correct 354 ms 8592 KB Output is correct
12 Correct 204 ms 8492 KB Output is correct
13 Correct 280 ms 8648 KB Output is correct
14 Correct 439 ms 8592 KB Output is correct
15 Correct 476 ms 9192 KB Output is correct
16 Correct 427 ms 9096 KB Output is correct
17 Correct 332 ms 8496 KB Output is correct
18 Correct 332 ms 8592 KB Output is correct
19 Correct 470 ms 9272 KB Output is correct
20 Correct 343 ms 8600 KB Output is correct
21 Correct 169 ms 9568 KB Output is correct
22 Correct 247 ms 9560 KB Output is correct
23 Correct 238 ms 9368 KB Output is correct
24 Correct 274 ms 9392 KB Output is correct
25 Correct 169 ms 8600 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3144 KB Output is correct
2 Correct 33 ms 3136 KB Output is correct
3 Correct 371 ms 9560 KB Output is correct
4 Correct 391 ms 10112 KB Output is correct
5 Correct 613 ms 10996 KB Output is correct
6 Correct 521 ms 10996 KB Output is correct
7 Correct 486 ms 10952 KB Output is correct
8 Correct 370 ms 10896 KB Output is correct
9 Correct 197 ms 8492 KB Output is correct
10 Correct 217 ms 8888 KB Output is correct
11 Correct 200 ms 9328 KB Output is correct
12 Correct 417 ms 10476 KB Output is correct
13 Correct 291 ms 10716 KB Output is correct
14 Correct 288 ms 10936 KB Output is correct
15 Correct 514 ms 10896 KB Output is correct
16 Correct 299 ms 9488 KB Output is correct
17 Correct 200 ms 9588 KB Output is correct
18 Correct 275 ms 9792 KB Output is correct
19 Correct 366 ms 9648 KB Output is correct
20 Correct 240 ms 9772 KB Output is correct
21 Correct 722 ms 10876 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3144 KB Output is correct
2 Correct 19 ms 3144 KB Output is correct
3 Correct 523 ms 9520 KB Output is correct
4 Correct 365 ms 9792 KB Output is correct
5 Correct 415 ms 10124 KB Output is correct
6 Correct 620 ms 10960 KB Output is correct
7 Correct 369 ms 9540 KB Output is correct
8 Correct 406 ms 9832 KB Output is correct
9 Correct 342 ms 9936 KB Output is correct
10 Correct 605 ms 10992 KB Output is correct
11 Correct 549 ms 10928 KB Output is correct
12 Correct 359 ms 10944 KB Output is correct
13 Correct 314 ms 9336 KB Output is correct
14 Correct 320 ms 8972 KB Output is correct
15 Correct 227 ms 9292 KB Output is correct
16 Correct 333 ms 8896 KB Output is correct
17 Correct 332 ms 9260 KB Output is correct
18 Correct 276 ms 9024 KB Output is correct
19 Correct 475 ms 10452 KB Output is correct
20 Correct 422 ms 10656 KB Output is correct
21 Correct 417 ms 11012 KB Output is correct
22 Correct 345 ms 10884 KB Output is correct
23 Correct 256 ms 10876 KB Output is correct
24 Correct 474 ms 10964 KB Output is correct
25 Correct 629 ms 10888 KB Output is correct
26 Correct 670 ms 10928 KB Output is correct
27 Correct 391 ms 9644 KB Output is correct
28 Correct 240 ms 9648 KB Output is correct
29 Correct 298 ms 9784 KB Output is correct
30 Correct 279 ms 9672 KB Output is correct
31 Correct 289 ms 9708 KB Output is correct
32 Correct 218 ms 9652 KB Output is correct
33 Correct 329 ms 9880 KB Output is correct
34 Correct 251 ms 9708 KB Output is correct
35 Correct 205 ms 9664 KB Output is correct
36 Correct 356 ms 9592 KB Output is correct
37 Correct 276 ms 9844 KB Output is correct
38 Correct 210 ms 9752 KB Output is correct
39 Correct 453 ms 10896 KB Output is correct
40 Correct 515 ms 10876 KB Output is correct
41 Correct 260 ms 10924 KB Output is correct
42 Correct 552 ms 11004 KB Output is correct