oj.uz

Submission #933909

# Submission time Handle Problem Language Result Execution time Memory
933909 2024-02-26T14:51:49 Z kim Highway Tolls (IOI18_highway) C++17
90 / 100
 196 ms 12520 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];

int 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=1,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 i;
        }
    }
}
int solve2(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=dist,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 i;
        }
    }
}
void solve3(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;
    solve3(solve2(solve1(0)));
    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 'int solve1(int)':
highway.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve2(int)':
highway.cpp:70:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void solve3(int)':
highway.cpp:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve1(int)':
highway.cpp:20:16: warning: control reaches end of non-void function [-Wreturn-type]
   20 |     queue<int> q;
      |                ^
highway.cpp: In function 'int solve2(int)':
highway.cpp:54:16: warning: control reaches end of non-void function [-Wreturn-type]
   54 |     queue<int> q;
      |                ^

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 2748 KB Output is correct
3 Correct 1 ms 2760 KB Output is correct
4 Correct 1 ms 3008 KB Output is correct
5 Correct 1 ms 2756 KB Output is correct
6 Correct 1 ms 2752 KB Output is correct
7 Correct 1 ms 2752 KB Output is correct
8 Correct 1 ms 3004 KB Output is correct
9 Correct 1 ms 2760 KB Output is correct
10 Correct 1 ms 2752 KB Output is correct
11 Correct 1 ms 2752 KB Output is correct
12 Correct 1 ms 3004 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2812 KB Output is correct
2 Correct 13 ms 3456 KB Output is correct
3 Correct 126 ms 10112 KB Output is correct
4 Correct 106 ms 9628 KB Output is correct
5 Correct 118 ms 10340 KB Output is correct
6 Correct 99 ms 9256 KB Output is correct
7 Correct 110 ms 9732 KB Output is correct
8 Correct 108 ms 9888 KB Output is correct
9 Correct 93 ms 9628 KB Output is correct
10 Correct 118 ms 10332 KB Output is correct
11 Correct 92 ms 8556 KB Output is correct
12 Correct 119 ms 8940 KB Output is correct
13 Correct 105 ms 9256 KB Output is correct
14 Correct 93 ms 8800 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3380 KB Output is correct
2 Correct 15 ms 4092 KB Output is correct
3 Correct 35 ms 4816 KB Output is correct
4 Correct 84 ms 8552 KB Output is correct
5 Correct 96 ms 8556 KB Output is correct
6 Correct 70 ms 8552 KB Output is correct
7 Correct 78 ms 8552 KB Output is correct
8 Correct 63 ms 8560 KB Output is correct
9 Correct 71 ms 8788 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2812 KB Output is correct
2 Correct 16 ms 3732 KB Output is correct
3 Correct 87 ms 7980 KB Output is correct
4 Correct 97 ms 9284 KB Output is correct
5 Correct 85 ms 9152 KB Output is correct
6 Correct 100 ms 9292 KB Output is correct
7 Correct 132 ms 9744 KB Output is correct
8 Correct 128 ms 9256 KB Output is correct
9 Correct 122 ms 9368 KB Output is correct
10 Correct 144 ms 9420 KB Output is correct
11 Correct 118 ms 8924 KB Output is correct
12 Correct 95 ms 8552 KB Output is correct
13 Correct 132 ms 8792 KB Output is correct
14 Correct 110 ms 8912 KB Output is correct
15 Correct 90 ms 9384 KB Output is correct
16 Correct 96 ms 9164 KB Output is correct
17 Correct 113 ms 8560 KB Output is correct
18 Correct 113 ms 8796 KB Output is correct
19 Correct 105 ms 9164 KB Output is correct
20 Correct 97 ms 8696 KB Output is correct
21 Correct 94 ms 10812 KB Output is correct
22 Correct 87 ms 10572 KB Output is correct
23 Correct 111 ms 10232 KB Output is correct
24 Correct 115 ms 10772 KB Output is correct
25 Correct 106 ms 8816 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3520 KB Output is correct
2 Correct 19 ms 3660 KB Output is correct
3 Correct 152 ms 10308 KB Output is correct
4 Correct 160 ms 11032 KB Output is correct
5 Correct 194 ms 12044 KB Output is correct
6 Correct 167 ms 12032 KB Output is correct
7 Correct 187 ms 12048 KB Output is correct
8 Correct 143 ms 11832 KB Output is correct
9 Correct 133 ms 10160 KB Output is correct
10 Correct 144 ms 10792 KB Output is correct
11 Correct 136 ms 11716 KB Output is correct
12 Correct 143 ms 11884 KB Output is correct
13 Correct 157 ms 12360 KB Output is correct
14 Correct 180 ms 12052 KB Output is correct
15 Correct 145 ms 11988 KB Output is correct
16 Correct 163 ms 11560 KB Output is correct
17 Correct 108 ms 10400 KB Output is correct
18 Correct 104 ms 11236 KB Output is correct
19 Correct 100 ms 10440 KB Output is correct
20 Correct 100 ms 11004 KB Output is correct
21 Correct 131 ms 11380 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3572 KB Output is correct
2 Correct 14 ms 3524 KB Output is correct
3 Correct 118 ms 9824 KB Output is correct
4 Correct 145 ms 10960 KB Output is correct
5 Correct 144 ms 10652 KB Output is correct
6 Correct 182 ms 12460 KB Output is correct
7 Correct 136 ms 10104 KB Output is correct
8 Correct 122 ms 10240 KB Output is correct
9 Correct 121 ms 10756 KB Output is correct
10 Correct 167 ms 11944 KB Output is correct
11 Correct 195 ms 11948 KB Output is correct
12 Correct 172 ms 12476 KB Output is correct
13 Correct 149 ms 11008 KB Output is correct
14 Correct 154 ms 10956 KB Output is correct
15 Correct 112 ms 11296 KB Output is correct
16 Correct 120 ms 11424 KB Output is correct
17 Correct 129 ms 11076 KB Output is correct
18 Correct 143 ms 11264 KB Output is correct
19 Correct 163 ms 12496 KB Output is correct
20 Correct 156 ms 12160 KB Output is correct
21 Correct 168 ms 12520 KB Output is correct
22 Correct 159 ms 12184 KB Output is correct
23 Correct 183 ms 12348 KB Output is correct
24 Correct 196 ms 12508 KB Output is correct
25 Correct 160 ms 12432 KB Output is correct
26 Correct 174 ms 11972 KB Output is correct
27 Correct 126 ms 11016 KB Output is correct
28 Correct 110 ms 10360 KB Output is correct
29 Partially correct 110 ms 10812 KB Output is partially correct
30 Partially correct 131 ms 10672 KB Output is partially correct
31 Correct 142 ms 10708 KB Output is correct
32 Partially correct 121 ms 11124 KB Output is partially correct
33 Correct 93 ms 11344 KB Output is correct
34 Correct 136 ms 10680 KB Output is correct
35 Partially correct 97 ms 10780 KB Output is partially correct
36 Correct 136 ms 10564 KB Output is correct
37 Correct 121 ms 10812 KB Output is correct
38 Partially correct 110 ms 10880 KB Output is partially correct
39 Correct 183 ms 11828 KB Output is correct
40 Correct 167 ms 11632 KB Output is correct
41 Correct 147 ms 11380 KB Output is correct
42 Correct 146 ms 11840 KB Output is correct