oj.uz

Submission #933897

# Submission time Handle Problem Language Result Execution time Memory
933897 2024-02-26T14:30:09 Z kim Highway Tolls (IOI18_highway) C++17
90 / 100
 218 ms 13352 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second

int n,m;
pii edge[130005];
vector<pii> graph[90005];
vector<int> tmp,ans;
ll mn_ask,dist;
bitset<90005> vis;
int tour[90005];

void solve1(int U){
    int id=0;
    queue<int> q;
    q.emplace(U);
    vis=0;
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        int u=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            q.emplace(v);
            tour[v]=++id;
        }
    }
    int l=0,r=id;
    while(l<r){
        int mid=l+r>>1;
        for(int i=0;i<m;++i){
            auto &[u,v]=edge[i];
            if(tour[u]<=mid&&tour[v]<=mid) tmp[i]=0;
            else tmp[i]=1;
        }
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    for(int i=0;i<n;++i){
        if(tour[i]==l){
            ans.eb(i);
            return;
        }
    }
}

void solve2(int U){
    queue<pii> q;
    q.emplace(U,0);
    vis=0;
    vis[U]=1;
    vector<int> tmp2(tmp.size(),1);
    vector<pii> vec;
    while(q.size()){
        auto [u,d]=q.front(); q.pop();
        for(auto &[v,id]:graph[u]){
            if(vis[v]) continue;
            if(d+1<dist) q.emplace(v,d+1), tmp2[id]=0;
            else if(d+1==dist) vec.eb(v,id);
            vis[v]=1;
        }
    }
    int l=0,r=vec.size();
    while(l<r){
        int mid=l+r>>1;
        tmp=tmp2;
        for(int i=0;i<=mid;++i) tmp[vec[i].s]=0;
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    ans.eb(vec[l].f);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N,m=U.size();
    for(int i=0;i<m;++i){
        edge[i]={U[i],V[i]};
        graph[U[i]].eb(V[i],i);
        graph[V[i]].eb(U[i],i);
    }
    tmp.assign(m,0);
    mn_ask=ask(tmp), dist=mn_ask/A;
    solve1(0);
    solve1(ans[0]);
    solve2(ans[1]);
    answer(ans[1],ans[2]);
}
/*
15 15  99 100  9 10
0 1
1 3
3 5
5 7
7 9
9 11
11 13
13 14
14 12
12 10
10 8
8 6
6 4
4 2
2 0
*/

Compilation message

highway.cpp: In function 'void solve1(int)':
highway.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void solve2(int)':
highway.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2752 KB Output is correct
2 Correct 1 ms 2752 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2756 KB Output is correct
5 Correct 1 ms 2756 KB Output is correct
6 Correct 1 ms 2760 KB Output is correct
7 Correct 1 ms 2760 KB Output is correct
8 Correct 1 ms 2760 KB Output is correct
9 Correct 1 ms 2760 KB Output is correct
10 Correct 1 ms 2756 KB Output is correct
11 Correct 1 ms 2756 KB Output is correct
12 Correct 1 ms 3008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2828 KB Output is correct
2 Correct 10 ms 3536 KB Output is correct
3 Correct 125 ms 10092 KB Output is correct
4 Correct 127 ms 9544 KB Output is correct
5 Correct 154 ms 9628 KB Output is correct
6 Correct 93 ms 9284 KB Output is correct
7 Correct 164 ms 10192 KB Output is correct
8 Correct 115 ms 9656 KB Output is correct
9 Correct 109 ms 9384 KB Output is correct
10 Correct 130 ms 10008 KB Output is correct
11 Correct 92 ms 9024 KB Output is correct
12 Correct 112 ms 9272 KB Output is correct
13 Correct 109 ms 9020 KB Output is correct
14 Correct 106 ms 9024 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3464 KB Output is correct
2 Correct 15 ms 4088 KB Output is correct
3 Correct 40 ms 4812 KB Output is correct
4 Correct 82 ms 8572 KB Output is correct
5 Correct 65 ms 8780 KB Output is correct
6 Correct 101 ms 8812 KB Output is correct
7 Correct 96 ms 8552 KB Output is correct
8 Correct 68 ms 8808 KB Output is correct
9 Correct 65 ms 8624 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2816 KB Output is correct
2 Correct 10 ms 3452 KB Output is correct
3 Correct 101 ms 7996 KB Output is correct
4 Correct 91 ms 9272 KB Output is correct
5 Correct 90 ms 9412 KB Output is correct
6 Correct 120 ms 9520 KB Output is correct
7 Correct 100 ms 9156 KB Output is correct
8 Correct 114 ms 9384 KB Output is correct
9 Correct 126 ms 9756 KB Output is correct
10 Correct 135 ms 10352 KB Output is correct
11 Correct 115 ms 9032 KB Output is correct
12 Correct 93 ms 9044 KB Output is correct
13 Correct 116 ms 9024 KB Output is correct
14 Correct 105 ms 9500 KB Output is correct
15 Correct 98 ms 9156 KB Output is correct
16 Correct 97 ms 9164 KB Output is correct
17 Correct 161 ms 9244 KB Output is correct
18 Correct 105 ms 9656 KB Output is correct
19 Correct 102 ms 9520 KB Output is correct
20 Correct 108 ms 9024 KB Output is correct
21 Correct 86 ms 10824 KB Output is correct
22 Correct 87 ms 10812 KB Output is correct
23 Correct 115 ms 10700 KB Output is correct
24 Correct 95 ms 10728 KB Output is correct
25 Correct 100 ms 9020 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3672 KB Output is correct
2 Correct 13 ms 3648 KB Output is correct
3 Correct 135 ms 10288 KB Output is correct
4 Correct 133 ms 11024 KB Output is correct
5 Correct 179 ms 12524 KB Output is correct
6 Correct 214 ms 12704 KB Output is correct
7 Correct 207 ms 12688 KB Output is correct
8 Correct 179 ms 12508 KB Output is correct
9 Correct 142 ms 10364 KB Output is correct
10 Correct 201 ms 10988 KB Output is correct
11 Correct 146 ms 11852 KB Output is correct
12 Correct 161 ms 11888 KB Output is correct
13 Correct 169 ms 13060 KB Output is correct
14 Correct 200 ms 12272 KB Output is correct
15 Correct 168 ms 12400 KB Output is correct
16 Correct 161 ms 11532 KB Output is correct
17 Correct 124 ms 11080 KB Output is correct
18 Correct 124 ms 10800 KB Output is correct
19 Correct 109 ms 10624 KB Output is correct
20 Correct 99 ms 11228 KB Output is correct
21 Correct 146 ms 11600 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3516 KB Output is correct
2 Correct 19 ms 3524 KB Output is correct
3 Correct 135 ms 10040 KB Output is correct
4 Correct 130 ms 10968 KB Output is correct
5 Correct 142 ms 11124 KB Output is correct
6 Correct 200 ms 12724 KB Output is correct
7 Correct 119 ms 10272 KB Output is correct
8 Correct 139 ms 10692 KB Output is correct
9 Correct 129 ms 11024 KB Output is correct
10 Correct 218 ms 11764 KB Output is correct
11 Correct 163 ms 12380 KB Output is correct
12 Correct 179 ms 12264 KB Output is correct
13 Correct 181 ms 10728 KB Output is correct
14 Correct 156 ms 11072 KB Output is correct
15 Correct 138 ms 11504 KB Output is correct
16 Correct 144 ms 11196 KB Output is correct
17 Correct 134 ms 11520 KB Output is correct
18 Correct 156 ms 11620 KB Output is correct
19 Correct 187 ms 12036 KB Output is correct
20 Correct 175 ms 11492 KB Output is correct
21 Correct 186 ms 12260 KB Output is correct
22 Correct 188 ms 12632 KB Output is correct
23 Correct 209 ms 12564 KB Output is correct
24 Correct 212 ms 13352 KB Output is correct
25 Correct 192 ms 12444 KB Output is correct
26 Correct 169 ms 12192 KB Output is correct
27 Correct 121 ms 10820 KB Output is correct
28 Partially correct 129 ms 10568 KB Output is partially correct
29 Partially correct 104 ms 11276 KB Output is partially correct
30 Correct 107 ms 11140 KB Output is correct
31 Correct 123 ms 10708 KB Output is correct
32 Partially correct 100 ms 10892 KB Output is partially correct
33 Correct 140 ms 11116 KB Output is correct
34 Correct 124 ms 10920 KB Output is correct
35 Correct 97 ms 10680 KB Output is correct
36 Partially correct 124 ms 10828 KB Output is partially correct
37 Correct 134 ms 10808 KB Output is correct
38 Partially correct 149 ms 11584 KB Output is partially correct
39 Correct 182 ms 12084 KB Output is correct
40 Correct 189 ms 12068 KB Output is correct
41 Correct 143 ms 11600 KB Output is correct
42 Correct 164 ms 11828 KB Output is correct