oj.uz

Submission #933942

# Submission time Handle Problem Language Result Execution time Memory
933942 2024-02-26T15:23:35 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 199 ms 23376 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=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;
        }
    }
}
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){
    using A=tuple<int,int,bool>;
    queue<A> q;
    q.emplace(U,0,0);
    vis=0;
    vis[U]=1;
    vector<int> tmp2(tmp.size(),1);
    vector<pii> vec;
    while(q.size()){
        auto [u,d,ok]=q.front(); q.pop();
        for(auto &[v,id]:graph[u]){
            if(vis[v]) continue;
            bool ok2=ok|(v==ans[0]);
            if(d+1<dist) q.emplace(v,d+1,ok2), tmp2[id]=0;
            else if(d+1==dist&&ok2) vec.eb(v,id);
            vis[v]=1;
        }
    }
    int l=0,r=(int)vec.size()-1;
    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:106:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         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 3008 KB Output is correct
2 Correct 1 ms 2756 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2752 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 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 2748 KB Output is correct
11 Correct 1 ms 2756 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 2816 KB Output is correct
2 Correct 14 ms 3452 KB Output is correct
3 Correct 111 ms 9520 KB Output is correct
4 Correct 115 ms 9056 KB Output is correct
5 Correct 103 ms 10112 KB Output is correct
6 Correct 91 ms 9276 KB Output is correct
7 Correct 96 ms 9300 KB Output is correct
8 Correct 120 ms 9064 KB Output is correct
9 Correct 85 ms 9540 KB Output is correct
10 Correct 122 ms 9520 KB Output is correct
11 Correct 109 ms 8692 KB Output is correct
12 Correct 112 ms 8940 KB Output is correct
13 Correct 96 ms 9176 KB Output is correct
14 Correct 96 ms 8692 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3464 KB Output is correct
2 Correct 15 ms 4012 KB Output is correct
3 Correct 35 ms 4636 KB Output is correct
4 Correct 78 ms 8452 KB Output is correct
5 Correct 59 ms 8460 KB Output is correct
6 Correct 64 ms 8708 KB Output is correct
7 Correct 82 ms 8460 KB Output is correct
8 Correct 69 ms 8712 KB Output is correct
9 Correct 73 ms 8696 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2820 KB Output is correct
2 Correct 9 ms 3460 KB Output is correct
3 Correct 84 ms 7940 KB Output is correct
4 Correct 91 ms 9268 KB Output is correct
5 Correct 81 ms 9504 KB Output is correct
6 Correct 111 ms 9528 KB Output is correct
7 Correct 82 ms 9296 KB Output is correct
8 Correct 113 ms 9508 KB Output is correct
9 Correct 122 ms 10248 KB Output is correct
10 Correct 129 ms 9280 KB Output is correct
11 Correct 102 ms 9168 KB Output is correct
12 Correct 91 ms 8460 KB Output is correct
13 Correct 144 ms 8940 KB Output is correct
14 Correct 107 ms 8912 KB Output is correct
15 Correct 88 ms 9236 KB Output is correct
16 Correct 113 ms 9464 KB Output is correct
17 Correct 109 ms 8704 KB Output is correct
18 Correct 105 ms 8916 KB Output is correct
19 Correct 91 ms 9280 KB Output is correct
20 Correct 100 ms 8668 KB Output is correct
21 Correct 83 ms 9292 KB Output is correct
22 Correct 90 ms 9292 KB Output is correct
23 Correct 111 ms 9600 KB Output is correct
24 Correct 93 ms 9532 KB Output is correct
25 Correct 90 ms 8576 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3500 KB Output is correct
2 Correct 16 ms 3520 KB Output is correct
3 Correct 124 ms 9764 KB Output is correct
4 Correct 130 ms 10300 KB Output is correct
5 Correct 199 ms 11408 KB Output is correct
6 Correct 159 ms 11864 KB Output is correct
7 Correct 150 ms 11876 KB Output is correct
8 Runtime error 151 ms 23376 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3572 KB Output is correct
2 Correct 14 ms 3556 KB Output is correct
3 Correct 128 ms 9788 KB Output is correct
4 Correct 150 ms 10024 KB Output is correct
5 Correct 187 ms 10448 KB Output is correct
6 Correct 151 ms 11660 KB Output is correct
7 Correct 133 ms 10220 KB Output is correct
8 Correct 120 ms 10436 KB Output is correct
9 Correct 143 ms 10496 KB Output is correct
10 Correct 136 ms 11904 KB Output is correct
11 Runtime error 166 ms 23136 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -