oj.uz

Submission #933922

# Submission time Handle Problem Language Result Execution time Memory
933922 2024-02-26T15:05:54 Z kim Highway Tolls (IOI18_highway) C++17
82 / 100
 200 ms 34868 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],adj[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<m;++i){
        auto &[u,v]=edge[i];
        if(tour[u]<=l&&tour[v]<=l) adj[u].eb(v,i),adj[v].eb(u,i);
    }
    for(int i=0;i<n;++i){
        if(tour[i]==l){
            ans.eb(i);
            return i;
        }
    }
}
using A=tuple<int,int,bool>;
void solve3(int U){
    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]:adj[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=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:102:27: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
  102 |             bool ok2=(ok|v==ans[0]);
highway.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         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 4868 KB Output is correct
2 Correct 1 ms 4868 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4876 KB Output is correct
5 Correct 1 ms 4872 KB Output is correct
6 Correct 1 ms 4876 KB Output is correct
7 Correct 1 ms 4880 KB Output is correct
8 Correct 1 ms 4872 KB Output is correct
9 Correct 1 ms 4872 KB Output is correct
10 Correct 2 ms 4864 KB Output is correct
11 Correct 1 ms 4872 KB Output is correct
12 Correct 1 ms 4872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 11 ms 5576 KB Output is correct
3 Correct 128 ms 12692 KB Output is correct
4 Correct 104 ms 14476 KB Output is correct
5 Correct 161 ms 13240 KB Output is correct
6 Correct 126 ms 14588 KB Output is correct
7 Correct 151 ms 13924 KB Output is correct
8 Correct 114 ms 11532 KB Output is correct
9 Correct 127 ms 14168 KB Output is correct
10 Correct 128 ms 14940 KB Output is correct
11 Correct 114 ms 11780 KB Output is correct
12 Correct 151 ms 12432 KB Output is correct
13 Correct 106 ms 12064 KB Output is correct
14 Correct 127 ms 11836 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5516 KB Output is correct
2 Correct 16 ms 6632 KB Output is correct
3 Correct 25 ms 6868 KB Output is correct
4 Correct 98 ms 11992 KB Output is correct
5 Correct 66 ms 10916 KB Output is correct
6 Correct 78 ms 13180 KB Output is correct
7 Correct 72 ms 10908 KB Output is correct
8 Correct 98 ms 12652 KB Output is correct
9 Correct 68 ms 10792 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4932 KB Output is correct
2 Correct 12 ms 5588 KB Output is correct
3 Correct 99 ms 9936 KB Output is correct
4 Correct 92 ms 11520 KB Output is correct
5 Correct 141 ms 11508 KB Output is correct
6 Correct 109 ms 11504 KB Output is correct
7 Correct 98 ms 11512 KB Output is correct
8 Correct 101 ms 11720 KB Output is correct
9 Correct 125 ms 13132 KB Output is correct
10 Correct 129 ms 13660 KB Output is correct
11 Correct 109 ms 12800 KB Output is correct
12 Correct 103 ms 13620 KB Output is correct
13 Correct 128 ms 12352 KB Output is correct
14 Correct 117 ms 12304 KB Output is correct
15 Correct 91 ms 11388 KB Output is correct
16 Correct 88 ms 11408 KB Output is correct
17 Correct 107 ms 12492 KB Output is correct
18 Correct 114 ms 12168 KB Output is correct
19 Correct 94 ms 11524 KB Output is correct
20 Correct 98 ms 10772 KB Output is correct
21 Correct 81 ms 12972 KB Output is correct
22 Correct 70 ms 14192 KB Output is correct
23 Correct 120 ms 15196 KB Output is correct
24 Correct 109 ms 15204 KB Output is correct
25 Correct 114 ms 13632 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5628 KB Output is correct
2 Correct 18 ms 5664 KB Output is correct
3 Correct 135 ms 12816 KB Output is correct
4 Correct 187 ms 13880 KB Output is correct
5 Correct 200 ms 15892 KB Output is correct
6 Correct 167 ms 16888 KB Output is correct
7 Correct 175 ms 14736 KB Output is correct
8 Runtime error 172 ms 34868 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 5624 KB Output is correct
2 Correct 16 ms 6032 KB Output is correct
3 Correct 153 ms 12156 KB Output is correct
4 Correct 145 ms 13996 KB Output is correct
5 Correct 131 ms 14164 KB Output is correct
6 Correct 163 ms 13756 KB Output is correct
7 Correct 155 ms 12512 KB Output is correct
8 Correct 119 ms 12820 KB Output is correct
9 Correct 149 ms 12940 KB Output is correct
10 Correct 161 ms 13752 KB Output is correct
11 Correct 150 ms 13972 KB Output is correct
12 Correct 160 ms 14796 KB Output is correct
13 Correct 198 ms 16748 KB Output is correct
14 Correct 157 ms 15524 KB Output is correct
15 Correct 125 ms 12668 KB Output is correct
16 Correct 141 ms 12956 KB Output is correct
17 Correct 152 ms 16176 KB Output is correct
18 Correct 150 ms 12844 KB Output is correct
19 Correct 167 ms 14292 KB Output is correct
20 Correct 156 ms 13692 KB Output is correct
21 Correct 168 ms 13672 KB Output is correct
22 Correct 166 ms 17072 KB Output is correct
23 Correct 156 ms 17332 KB Output is correct
24 Correct 179 ms 15512 KB Output is correct
25 Correct 145 ms 13972 KB Output is correct
26 Correct 172 ms 13964 KB Output is correct
27 Correct 130 ms 13316 KB Output is correct
28 Correct 98 ms 12280 KB Output is correct
29 Correct 112 ms 12640 KB Output is correct
30 Correct 120 ms 12284 KB Output is correct
31 Correct 97 ms 12660 KB Output is correct
32 Correct 110 ms 13312 KB Output is correct
33 Correct 119 ms 14184 KB Output is correct
34 Correct 120 ms 12832 KB Output is correct
35 Correct 104 ms 12060 KB Output is correct
36 Correct 125 ms 12060 KB Output is correct
37 Correct 131 ms 12556 KB Output is correct
38 Correct 114 ms 13864 KB Output is correct
39 Correct 155 ms 14048 KB Output is correct
40 Correct 189 ms 14280 KB Output is correct
41 Correct 161 ms 17472 KB Output is correct
42 Correct 157 ms 14008 KB Output is correct