oj.uz

Submission #933950

# Submission time Handle Problem Language Result Execution time Memory
933950 2024-02-26T15:29:24 Z kim Highway Tolls (IOI18_highway) C++17
82 / 100
 205 ms 24068 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;
int vis[90005];
int tour[90005];

int solve1(int U){
    int id=0;
    queue<int> q;
    q.emplace(U);
    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);
    for(int i=0;i<n;++i) vis[i]=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){
        graph[i].clear();
        if(tour[i]==l) ans.eb(i);
    }
    for(int i=0;i<m;++i){
        auto &[u,v]=edge[i];
        if(tour[u]<=l&&tour[v]<=l) graph[u].eb(v,i),graph[v].eb(u,i);
    }
    return ans.back();
}
void solve3(int U){
    using A=tuple<int,bool>;
    queue<A> q;
    q.emplace(U,0);
    for(int i=0;i<n;++i) vis[i]=-1;
    vis[U]=0;
    vector<int> tmp2(tmp.size(),1);
    vector<pii> vec;
    while(q.size()){
        auto [u,ok]=q.front(); q.pop();
        for(auto &[v,id]:graph[u]){
            if(vis[v]!=-1) continue;
            bool ok2=ok|(v==ans[0]);
            vis[v]=vis[u]+1;
            if(vis[v]<dist) q.emplace(v,ok2), tmp2[id]=0;
            else if(vis[v]==dist&&ok2) vec.eb(v,id);
        }
    }
    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:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve2(int)':
highway.cpp:69:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void solve3(int)':
highway.cpp:108:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         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;
      |                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3100 KB Output is correct
2 Correct 1 ms 3096 KB Output is correct
3 Correct 1 ms 3096 KB Output is correct
4 Correct 1 ms 3100 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 3096 KB Output is correct
7 Correct 1 ms 3156 KB Output is correct
8 Correct 1 ms 3096 KB Output is correct
9 Correct 1 ms 3096 KB Output is correct
10 Correct 1 ms 3092 KB Output is correct
11 Correct 1 ms 3096 KB Output is correct
12 Correct 1 ms 3096 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 14 ms 3784 KB Output is correct
3 Correct 103 ms 9856 KB Output is correct
4 Correct 94 ms 9840 KB Output is correct
5 Correct 111 ms 9856 KB Output is correct
6 Correct 119 ms 9380 KB Output is correct
7 Correct 96 ms 9836 KB Output is correct
8 Correct 122 ms 9388 KB Output is correct
9 Correct 90 ms 9624 KB Output is correct
10 Correct 97 ms 10076 KB Output is correct
11 Correct 118 ms 9016 KB Output is correct
12 Correct 126 ms 9716 KB Output is correct
13 Correct 132 ms 9252 KB Output is correct
14 Correct 114 ms 9272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3716 KB Output is correct
2 Correct 13 ms 4600 KB Output is correct
3 Correct 26 ms 4964 KB Output is correct
4 Correct 87 ms 8792 KB Output is correct
5 Correct 74 ms 8864 KB Output is correct
6 Correct 89 ms 8788 KB Output is correct
7 Correct 86 ms 8804 KB Output is correct
8 Correct 116 ms 8788 KB Output is correct
9 Correct 116 ms 9016 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 12 ms 3992 KB Output is correct
3 Correct 90 ms 8092 KB Output is correct
4 Correct 93 ms 9376 KB Output is correct
5 Correct 106 ms 9836 KB Output is correct
6 Correct 95 ms 9616 KB Output is correct
7 Correct 105 ms 9632 KB Output is correct
8 Correct 99 ms 9844 KB Output is correct
9 Correct 127 ms 9860 KB Output is correct
10 Correct 145 ms 10340 KB Output is correct
11 Correct 145 ms 9028 KB Output is correct
12 Correct 101 ms 8852 KB Output is correct
13 Correct 96 ms 9272 KB Output is correct
14 Correct 103 ms 9264 KB Output is correct
15 Correct 96 ms 9388 KB Output is correct
16 Correct 90 ms 9616 KB Output is correct
17 Correct 108 ms 9272 KB Output is correct
18 Correct 107 ms 9320 KB Output is correct
19 Correct 107 ms 10112 KB Output is correct
20 Correct 93 ms 9004 KB Output is correct
21 Correct 81 ms 9856 KB Output is correct
22 Correct 96 ms 9876 KB Output is correct
23 Correct 126 ms 9928 KB Output is correct
24 Correct 103 ms 10076 KB Output is correct
25 Correct 93 ms 8908 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4184 KB Output is correct
2 Correct 14 ms 4120 KB Output is correct
3 Correct 131 ms 10076 KB Output is correct
4 Correct 159 ms 11512 KB Output is correct
5 Correct 170 ms 11492 KB Output is correct
6 Correct 170 ms 12300 KB Output is correct
7 Correct 185 ms 11944 KB Output is correct
8 Runtime error 175 ms 24068 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4084 KB Output is correct
2 Correct 18 ms 4112 KB Output is correct
3 Correct 112 ms 10112 KB Output is correct
4 Correct 128 ms 10576 KB Output is correct
5 Correct 130 ms 10836 KB Output is correct
6 Correct 147 ms 12176 KB Output is correct
7 Correct 111 ms 10572 KB Output is correct
8 Correct 168 ms 10292 KB Output is correct
9 Correct 113 ms 10836 KB Output is correct
10 Correct 188 ms 12172 KB Output is correct
11 Correct 179 ms 11740 KB Output is correct
12 Correct 148 ms 11712 KB Output is correct
13 Correct 144 ms 11332 KB Output is correct
14 Correct 143 ms 11392 KB Output is correct
15 Correct 138 ms 11028 KB Output is correct
16 Correct 147 ms 11336 KB Output is correct
17 Correct 120 ms 10660 KB Output is correct
18 Correct 192 ms 11216 KB Output is correct
19 Correct 201 ms 12208 KB Output is correct
20 Correct 159 ms 12044 KB Output is correct
21 Correct 201 ms 12632 KB Output is correct
22 Correct 143 ms 12408 KB Output is correct
23 Correct 164 ms 12596 KB Output is correct
24 Correct 199 ms 11752 KB Output is correct
25 Correct 159 ms 12140 KB Output is correct
26 Correct 150 ms 12196 KB Output is correct
27 Correct 107 ms 10508 KB Output is correct
28 Correct 95 ms 10228 KB Output is correct
29 Correct 143 ms 10504 KB Output is correct
30 Correct 102 ms 10288 KB Output is correct
31 Correct 115 ms 10492 KB Output is correct
32 Correct 99 ms 10180 KB Output is correct
33 Correct 110 ms 10188 KB Output is correct
34 Correct 102 ms 10004 KB Output is correct
35 Correct 94 ms 10104 KB Output is correct
36 Correct 93 ms 9944 KB Output is correct
37 Correct 123 ms 10588 KB Output is correct
38 Correct 149 ms 10344 KB Output is correct
39 Correct 185 ms 12160 KB Output is correct
40 Correct 155 ms 11908 KB Output is correct
41 Correct 140 ms 11696 KB Output is correct
42 Correct 205 ms 12348 KB Output is correct