oj.uz

Submission #915413

# Submission time Handle Problem Language Result Execution time Memory
915413 2024-01-23T20:11:27 Z biank Highway Tolls (IOI18_highway) C++14
100 / 100
 202 ms 12496 KB 
#include <bits/stdc++.h>
using namespace std;
#define SIZE(x) int(x.size())
#define forn(i,n) for(int i=0;i<int(n);i++)
#define pb push_back
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
ll ask(const vi &w);
void answer(int s, int t);
void find_pair(int n, vi u, vi v, int /*a*/, int /*b*/) {
    vector<vii> adj(n);
    int m=SIZE(u);
    forn(i,m) {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
    }
    
    vi w(m,0);
    ll D=ask(w);
    
    int low=-1, high=m;
    while(high-low>1) {
        int mid=(low+high)/2;
        forn(i,m) w[i]=i<=mid;
        if(ask(w)!=D) high=mid;
        else low=mid;
    }
    
    int e=high;
    int start[2]={u[e],v[e]};
    vi d[2];
    forn(i,2) {
        d[i].assign(n,-1);
        queue<int> q;
        q.push(start[i]);
        d[i][start[i]]=0;
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            for(auto [y,__]:adj[x]) {
                if(d[i][y]==-1) {
                    q.push(y);
                    d[i][y]=d[i][x]+1;
                }
            }
        }
    }
    
    int ans[2];
    forn(i,2) {
        vi node(n,0), edge(m,-1), dist(n,-1);
        queue<int> q;
        int c=0;
        q.push(start[i]);
        dist[start[i]]=0;
        
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            for(auto [y,idx]:adj[x]) {
                if(d[i][y]<d[1-i][y] && dist[y]==-1) {
                    dist[y]=dist[x]+1;
                    node[c]=y;
                    edge[idx]=c++;
                    q.push(y);
                } else if((d[i][y]>=d[1-i][y] && idx!=e)||dist[y]==dist[x]+1) {
                    edge[idx]=n;
                }
            }
        }
        
        int lo=-1, hi=c;
        while(hi-lo>1) {
            int mid=(lo+hi)/2;
            forn(j,m) w[j]=edge[j]>=mid;
            if(ask(w)!=D) lo=mid;
            else hi=mid;
        }
        if(lo==-1) ans[i]=start[i];
        else ans[i]=node[lo];
    }
    
    answer(ans[0],ans[1]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:42:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             for(auto [y,__]:adj[x]) {
      |                      ^
highway.cpp:62:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |             for(auto [y,idx]:adj[x]) {
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 1 ms 444 KB Output is correct
12 Correct 1 ms 444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 12 ms 1456 KB Output is correct
3 Correct 114 ms 9488 KB Output is correct
4 Correct 93 ms 9720 KB Output is correct
5 Correct 119 ms 9716 KB Output is correct
6 Correct 78 ms 9720 KB Output is correct
7 Correct 103 ms 10196 KB Output is correct
8 Correct 128 ms 9484 KB Output is correct
9 Correct 107 ms 9484 KB Output is correct
10 Correct 114 ms 9936 KB Output is correct
11 Correct 100 ms 9360 KB Output is correct
12 Correct 96 ms 9312 KB Output is correct
13 Correct 94 ms 9124 KB Output is correct
14 Correct 88 ms 8920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 15 ms 2352 KB Output is correct
3 Correct 23 ms 3508 KB Output is correct
4 Correct 88 ms 8896 KB Output is correct
5 Correct 69 ms 9136 KB Output is correct
6 Correct 98 ms 8924 KB Output is correct
7 Correct 91 ms 8880 KB Output is correct
8 Correct 66 ms 9148 KB Output is correct
9 Correct 73 ms 8888 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 14 ms 1464 KB Output is correct
3 Correct 57 ms 7500 KB Output is correct
4 Correct 118 ms 9468 KB Output is correct
5 Correct 80 ms 9484 KB Output is correct
6 Correct 74 ms 9472 KB Output is correct
7 Correct 108 ms 9480 KB Output is correct
8 Correct 145 ms 9692 KB Output is correct
9 Correct 87 ms 9708 KB Output is correct
10 Correct 85 ms 9940 KB Output is correct
11 Correct 84 ms 8920 KB Output is correct
12 Correct 93 ms 9356 KB Output is correct
13 Correct 91 ms 9340 KB Output is correct
14 Correct 97 ms 9324 KB Output is correct
15 Correct 86 ms 9484 KB Output is correct
16 Correct 84 ms 9712 KB Output is correct
17 Correct 92 ms 8888 KB Output is correct
18 Correct 89 ms 8880 KB Output is correct
19 Correct 78 ms 9508 KB Output is correct
20 Correct 83 ms 8892 KB Output is correct
21 Correct 122 ms 10040 KB Output is correct
22 Correct 103 ms 9964 KB Output is correct
23 Correct 77 ms 10020 KB Output is correct
24 Correct 81 ms 9904 KB Output is correct
25 Correct 87 ms 9236 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1588 KB Output is correct
2 Correct 12 ms 1540 KB Output is correct
3 Correct 99 ms 10060 KB Output is correct
4 Correct 138 ms 10636 KB Output is correct
5 Correct 137 ms 11640 KB Output is correct
6 Correct 121 ms 11632 KB Output is correct
7 Correct 131 ms 11816 KB Output is correct
8 Correct 131 ms 11868 KB Output is correct
9 Correct 147 ms 7732 KB Output is correct
10 Correct 120 ms 7988 KB Output is correct
11 Correct 151 ms 8964 KB Output is correct
12 Correct 136 ms 10712 KB Output is correct
13 Correct 202 ms 11184 KB Output is correct
14 Correct 189 ms 11900 KB Output is correct
15 Correct 125 ms 11868 KB Output is correct
16 Correct 132 ms 9568 KB Output is correct
17 Correct 86 ms 10020 KB Output is correct
18 Correct 92 ms 10668 KB Output is correct
19 Correct 74 ms 10200 KB Output is correct
20 Correct 80 ms 10232 KB Output is correct
21 Correct 129 ms 11836 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1592 KB Output is correct
2 Correct 17 ms 1556 KB Output is correct
3 Correct 105 ms 10600 KB Output is correct
4 Correct 100 ms 10300 KB Output is correct
5 Correct 172 ms 10852 KB Output is correct
6 Correct 128 ms 11868 KB Output is correct
7 Correct 106 ms 9936 KB Output is correct
8 Correct 102 ms 10272 KB Output is correct
9 Correct 115 ms 10708 KB Output is correct
10 Correct 138 ms 11644 KB Output is correct
11 Correct 134 ms 12296 KB Output is correct
12 Correct 127 ms 11836 KB Output is correct
13 Correct 95 ms 8764 KB Output is correct
14 Correct 106 ms 7988 KB Output is correct
15 Correct 139 ms 9024 KB Output is correct
16 Correct 119 ms 7988 KB Output is correct
17 Correct 128 ms 9012 KB Output is correct
18 Correct 99 ms 8052 KB Output is correct
19 Correct 136 ms 11296 KB Output is correct
20 Correct 128 ms 11724 KB Output is correct
21 Correct 130 ms 12336 KB Output is correct
22 Correct 130 ms 11636 KB Output is correct
23 Correct 138 ms 12496 KB Output is correct
24 Correct 139 ms 11868 KB Output is correct
25 Correct 128 ms 12344 KB Output is correct
26 Correct 130 ms 11872 KB Output is correct
27 Correct 83 ms 10400 KB Output is correct
28 Correct 132 ms 10076 KB Output is correct
29 Correct 81 ms 10412 KB Output is correct
30 Correct 141 ms 10164 KB Output is correct
31 Correct 104 ms 10356 KB Output is correct
32 Correct 89 ms 10052 KB Output is correct
33 Correct 82 ms 10280 KB Output is correct
34 Correct 86 ms 10224 KB Output is correct
35 Correct 79 ms 10104 KB Output is correct
36 Correct 82 ms 10496 KB Output is correct
37 Correct 102 ms 10244 KB Output is correct
38 Correct 91 ms 10632 KB Output is correct
39 Correct 133 ms 11888 KB Output is correct
40 Correct 186 ms 12068 KB Output is correct
41 Correct 123 ms 11620 KB Output is correct
42 Correct 153 ms 12020 KB Output is correct