oj.uz

Submission #933904

# Submission time Handle Problem Language Result Execution time Memory
933904 2024-02-26T14:47:24 Z kim Highway Tolls (IOI18_highway) C++17
30 / 100
 226 ms 12496 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<pii> q;
    q.emplace(U,0);
    vis=0;
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        auto [u,d]=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            if(d+1<dist) q.emplace(v,d+1);
            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;
        }
    }
}
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<pii> 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 2756 KB Output is correct
3 Correct 1 ms 2756 KB Output is correct
4 Correct 1 ms 2760 KB Output is correct
5 Correct 1 ms 2756 KB Output is correct
6 Correct 1 ms 2756 KB Output is correct
7 Correct 1 ms 2756 KB Output is correct
8 Correct 1 ms 2752 KB Output is correct
9 Correct 1 ms 2748 KB Output is correct
10 Correct 1 ms 2756 KB Output is correct
11 Correct 1 ms 2752 KB Output is correct
12 Correct 1 ms 2756 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2812 KB Output is correct
2 Correct 10 ms 3532 KB Output is correct
3 Correct 107 ms 10096 KB Output is correct
4 Correct 107 ms 9860 KB Output is correct
5 Correct 114 ms 9884 KB Output is correct
6 Correct 94 ms 9428 KB Output is correct
7 Correct 104 ms 10432 KB Output is correct
8 Correct 103 ms 9416 KB Output is correct
9 Correct 88 ms 9468 KB Output is correct
10 Correct 111 ms 10268 KB Output is correct
11 Correct 98 ms 9036 KB Output is correct
12 Correct 103 ms 9172 KB Output is correct
13 Correct 101 ms 9252 KB Output is correct
14 Correct 89 ms 8800 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3464 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2816 KB Output is correct
2 Correct 15 ms 3588 KB Output is correct
3 Incorrect 64 ms 8036 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3576 KB Output is correct
2 Correct 13 ms 3984 KB Output is correct
3 Correct 127 ms 10484 KB Output is correct
4 Correct 121 ms 11024 KB Output is correct
5 Correct 161 ms 12496 KB Output is correct
6 Correct 226 ms 12460 KB Output is correct
7 Correct 166 ms 12264 KB Output is correct
8 Correct 157 ms 11844 KB Output is correct
9 Correct 127 ms 10680 KB Output is correct
10 Correct 115 ms 11700 KB Output is correct
11 Correct 128 ms 11300 KB Output is correct
12 Correct 134 ms 11700 KB Output is correct
13 Correct 151 ms 11944 KB Output is correct
14 Correct 170 ms 11836 KB Output is correct
15 Correct 137 ms 11984 KB Output is correct
16 Correct 142 ms 11580 KB Output is correct
17 Correct 105 ms 11012 KB Output is correct
18 Correct 104 ms 11100 KB Output is correct
19 Correct 100 ms 10484 KB Output is correct
20 Correct 102 ms 11172 KB Output is correct
21 Correct 127 ms 11608 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3576 KB Output is correct
2 Correct 14 ms 3532 KB Output is correct
3 Correct 111 ms 10260 KB Output is correct
4 Incorrect 134 ms 10580 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -