oj.uz

Submission #854355

# Submission time Handle Problem Language Result Execution time Memory
854355 2023-09-27T03:40:38 Z abcvuitunggio Highway Tolls (IOI18_highway) C++17
100 / 100
 126 ms 11160 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int M,d[90001][2],type[90001],S,T;
vector <int> ke[90001];
vector <pair <int, int>> a,b;
queue <int> q;
void bfs(int s, int i){
    d[s][i]=0;
    q.push(s);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int v:ke[u])
            if (d[v][i]==-1){
                d[v][i]=d[u][i]+1;
                q.push(v);
            }
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    M=U.size();
    memset(d,-1,sizeof(d));
    vector <int> w(M,0);
    long long dist=ask(w);
    int l=0,r=M-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            w[i]=1;
        if (ask(w)>dist){
            kq=mid;
            r=mid-1;
        }
        else
            l=mid+1;
        for (int i=0;i<=mid;i++)
            w[i]=0;
    }
    for (int i=kq+1;i<M;i++){
        ke[U[i]].push_back(V[i]);
        ke[V[i]].push_back(U[i]);
    }
    for (int i=0;i<kq;i++)
        w[i]=1;
    bfs(U[kq],0);
    bfs(V[kq],1);
    for (int i=0;i<N;i++){
        if (d[i][0]==-1&&d[i][1]==-1)
            continue;
        if (d[i][0]==-1)
            d[i][0]=1e9;
        if (d[i][1]==-1)
            d[i][1]=1e9;
        if (d[i][1]>d[i][0]+1)
            type[i]=1;
        if (d[i][0]>d[i][1]+1)
            type[i]=2;
    }
    for (int i=kq+1;i<M;i++){
        if (type[U[i]]==1&&type[V[i]]==1)
            a.emplace_back(max(d[U[i]][0],d[V[i]][0]),i);
        if (type[U[i]]==2&&type[V[i]]==2)
            b.emplace_back(max(d[U[i]][1],d[V[i]][1]),i);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int tmp=kq;
    l=0,r=a.size()-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=mid;i<a.size();i++)
            w[a[i].second]=1;
        if (ask(w)>dist){
            kq=a[mid].second;
            l=mid+1;
        }
        else
            r=mid-1;
        for (int i=mid;i<a.size();i++)
            w[a[i].second]=0;
    }
    S=(kq==-1?U[tmp]:(d[U[kq]][0]>d[V[kq]][0]?U[kq]:V[kq]));
    l=0,r=b.size()-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=mid;i<b.size();i++)
            w[b[i].second]=1;
        if (ask(w)>dist){
            kq=b[mid].second;
            l=mid+1;
        }
        else
            r=mid-1;
        for (int i=mid;i<b.size();i++)
            w[b[i].second]=0;
    }
    T=(kq==-1?V[tmp]:(d[U[kq]][1]>d[V[kq]][1]?U[kq]:V[kq]));
    answer(S,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:72:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:95:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3376 KB Output is correct
2 Correct 1 ms 3376 KB Output is correct
3 Correct 1 ms 3368 KB Output is correct
4 Correct 1 ms 3368 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3368 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3376 KB Output is correct
10 Correct 1 ms 3372 KB Output is correct
11 Correct 1 ms 3372 KB Output is correct
12 Correct 1 ms 3376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3384 KB Output is correct
2 Correct 11 ms 4252 KB Output is correct
3 Correct 77 ms 9344 KB Output is correct
4 Correct 84 ms 9360 KB Output is correct
5 Correct 82 ms 9336 KB Output is correct
6 Correct 75 ms 8940 KB Output is correct
7 Correct 73 ms 8568 KB Output is correct
8 Correct 90 ms 9372 KB Output is correct
9 Correct 75 ms 8644 KB Output is correct
10 Correct 79 ms 8872 KB Output is correct
11 Correct 68 ms 8376 KB Output is correct
12 Correct 83 ms 9320 KB Output is correct
13 Correct 89 ms 9448 KB Output is correct
14 Correct 96 ms 9424 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3988 KB Output is correct
2 Correct 14 ms 4636 KB Output is correct
3 Correct 18 ms 4140 KB Output is correct
4 Correct 62 ms 7912 KB Output is correct
5 Correct 63 ms 7932 KB Output is correct
6 Correct 59 ms 8820 KB Output is correct
7 Correct 55 ms 5392 KB Output is correct
8 Correct 68 ms 7968 KB Output is correct
9 Correct 56 ms 6268 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3388 KB Output is correct
2 Correct 10 ms 4160 KB Output is correct
3 Correct 62 ms 8400 KB Output is correct
4 Correct 77 ms 9288 KB Output is correct
5 Correct 63 ms 8200 KB Output is correct
6 Correct 61 ms 8192 KB Output is correct
7 Correct 69 ms 8816 KB Output is correct
8 Correct 61 ms 8208 KB Output is correct
9 Correct 84 ms 9428 KB Output is correct
10 Correct 83 ms 8996 KB Output is correct
11 Correct 93 ms 9284 KB Output is correct
12 Correct 80 ms 9072 KB Output is correct
13 Correct 90 ms 9116 KB Output is correct
14 Correct 75 ms 8500 KB Output is correct
15 Correct 66 ms 8032 KB Output is correct
16 Correct 58 ms 7248 KB Output is correct
17 Correct 89 ms 9332 KB Output is correct
18 Correct 84 ms 9336 KB Output is correct
19 Correct 62 ms 8064 KB Output is correct
20 Correct 62 ms 8232 KB Output is correct
21 Correct 60 ms 8056 KB Output is correct
22 Correct 68 ms 6600 KB Output is correct
23 Correct 77 ms 9804 KB Output is correct
24 Correct 77 ms 9764 KB Output is correct
25 Correct 80 ms 9388 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4180 KB Output is correct
2 Correct 11 ms 4120 KB Output is correct
3 Correct 102 ms 9528 KB Output is correct
4 Correct 92 ms 9280 KB Output is correct
5 Correct 112 ms 10092 KB Output is correct
6 Correct 106 ms 10000 KB Output is correct
7 Correct 102 ms 9692 KB Output is correct
8 Correct 106 ms 9880 KB Output is correct
9 Correct 75 ms 5936 KB Output is correct
10 Correct 89 ms 7384 KB Output is correct
11 Correct 83 ms 7676 KB Output is correct
12 Correct 92 ms 9480 KB Output is correct
13 Correct 101 ms 9652 KB Output is correct
14 Correct 113 ms 9976 KB Output is correct
15 Correct 114 ms 10016 KB Output is correct
16 Correct 92 ms 8160 KB Output is correct
17 Correct 73 ms 9340 KB Output is correct
18 Correct 70 ms 7928 KB Output is correct
19 Correct 78 ms 9504 KB Output is correct
20 Correct 74 ms 8676 KB Output is correct
21 Correct 120 ms 11160 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4012 KB Output is correct
2 Correct 11 ms 4268 KB Output is correct
3 Correct 94 ms 9412 KB Output is correct
4 Correct 100 ms 9348 KB Output is correct
5 Correct 100 ms 9532 KB Output is correct
6 Correct 112 ms 9688 KB Output is correct
7 Correct 91 ms 9904 KB Output is correct
8 Correct 99 ms 9668 KB Output is correct
9 Correct 99 ms 9124 KB Output is correct
10 Correct 115 ms 9784 KB Output is correct
11 Correct 104 ms 9832 KB Output is correct
12 Correct 115 ms 9768 KB Output is correct
13 Correct 73 ms 5984 KB Output is correct
14 Correct 72 ms 6624 KB Output is correct
15 Correct 90 ms 7968 KB Output is correct
16 Correct 94 ms 7532 KB Output is correct
17 Correct 84 ms 7828 KB Output is correct
18 Correct 82 ms 7032 KB Output is correct
19 Correct 93 ms 9516 KB Output is correct
20 Correct 110 ms 9944 KB Output is correct
21 Correct 105 ms 10288 KB Output is correct
22 Correct 116 ms 9924 KB Output is correct
23 Correct 103 ms 9728 KB Output is correct
24 Correct 113 ms 9948 KB Output is correct
25 Correct 118 ms 9880 KB Output is correct
26 Correct 114 ms 9924 KB Output is correct
27 Correct 67 ms 8936 KB Output is correct
28 Correct 67 ms 9272 KB Output is correct
29 Correct 75 ms 10080 KB Output is correct
30 Correct 75 ms 9784 KB Output is correct
31 Correct 76 ms 9744 KB Output is correct
32 Correct 73 ms 9744 KB Output is correct
33 Correct 69 ms 10024 KB Output is correct
34 Correct 74 ms 8836 KB Output is correct
35 Correct 71 ms 9132 KB Output is correct
36 Correct 69 ms 9744 KB Output is correct
37 Correct 72 ms 9360 KB Output is correct
38 Correct 78 ms 9568 KB Output is correct
39 Correct 126 ms 10664 KB Output is correct
40 Correct 123 ms 11108 KB Output is correct
41 Correct 120 ms 10548 KB Output is correct
42 Correct 125 ms 10560 KB Output is correct