oj.uz

Submission #438957

# Submission time Handle Problem Language Result Execution time Memory
438957 2021-06-29T01:42:30 Z leinad2 Highway Tolls (IOI18_highway) C++17
100 / 100
 282 ms 11004 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> >adj[90010];
int vis[90010];
void find_pair(int N, vector<int>U, vector<int>V, int A, int B)
{
    int M=U.size();
    vector<int>w(M);long long X=ask(w);
    for(int i=0;i<M;i++)
    {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    int s=0;int e=M-1;
    while(s<e)
    {
        int m=s+e>>1;
        for(int i=0;i<M;i++)w[i]=0;
        for(int i=0;i<=m;i++)w[i]=1;
        if(ask(w)>X)e=m;
        else s=m+1;
    }
    int S=U[s], E=V[s];
    queue<pair<int, int> >q;
    q.push({S, 0});
    q.push({E, 1});
    vis[S]=vis[E]=1;
    vector<int>v1, v2;
    while(q.size())
    {
        int a=q.front().first;int b=q.front().second;q.pop();
        if(b==0)v1.push_back(a);else v2.push_back(a);
        for(int i=0;i<adj[a].size();i++)
        {
            int p=adj[a][i].first;
            if(vis[p])continue;
            vis[p]=1;q.push({p, b});
        }
    }
    int a=0;int b=v1.size()-1;
    while(a<b)
    {
        int chk[90010]={};
        int m=a+b+1>>1;
        for(int i=0;i<N;i++)chk[i]=0;
        for(int i=m;i<v1.size();i++)chk[v1[i]]=1;
        for(int i=0;i<M;i++)w[i]=(chk[U[i]]!=chk[V[i]]);
        if(ask(w)>X)a=m;
        else b=m-1;
    }
    int ans1=v1[a];
    a=0;b=v2.size()-1;
    while(a<b)
    {
        int chk[90010]={};
        int m=a+b+1>>1;
        for(int i=0;i<N;i++)chk[i]=0;
        for(int i=m;i<v2.size();i++)chk[v2[i]]=1;
        for(int i=0;i<M;i++)w[i]=(chk[U[i]]!=chk[V[i]]);
        if(ask(w)>X)a=m;
        else b=m-1;
    }
    int ans2=v2[a];
    answer(ans1, ans2);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int m=s+e>>1;
      |               ~^~
highway.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i=0;i<adj[a].size();i++)
      |                     ~^~~~~~~~~~~~~~
highway.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m=a+b+1>>1;
      |               ~~~^~
highway.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=m;i<v1.size();i++)chk[v1[i]]=1;
      |                     ~^~~~~~~~~~
highway.cpp:57:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int m=a+b+1>>1;
      |               ~~~^~
highway.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=m;i<v2.size();i++)chk[v2[i]]=1;
      |                     ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2760 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2760 KB Output is correct
4 Correct 2 ms 2760 KB Output is correct
5 Correct 2 ms 2760 KB Output is correct
6 Correct 2 ms 2760 KB Output is correct
7 Correct 2 ms 2760 KB Output is correct
8 Correct 2 ms 2760 KB Output is correct
9 Correct 3 ms 2760 KB Output is correct
10 Correct 2 ms 2760 KB Output is correct
11 Correct 3 ms 2760 KB Output is correct
12 Correct 3 ms 2760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2760 KB Output is correct
2 Correct 14 ms 3460 KB Output is correct
3 Correct 140 ms 8916 KB Output is correct
4 Correct 142 ms 8864 KB Output is correct
5 Correct 130 ms 8956 KB Output is correct
6 Correct 239 ms 8948 KB Output is correct
7 Correct 141 ms 9084 KB Output is correct
8 Correct 151 ms 9000 KB Output is correct
9 Correct 261 ms 8936 KB Output is correct
10 Correct 143 ms 8864 KB Output is correct
11 Correct 160 ms 8244 KB Output is correct
12 Correct 200 ms 8408 KB Output is correct
13 Correct 132 ms 8276 KB Output is correct
14 Correct 147 ms 8320 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3388 KB Output is correct
2 Correct 27 ms 3908 KB Output is correct
3 Correct 37 ms 4632 KB Output is correct
4 Correct 175 ms 8252 KB Output is correct
5 Correct 115 ms 8224 KB Output is correct
6 Correct 225 ms 8352 KB Output is correct
7 Correct 205 ms 8188 KB Output is correct
8 Correct 105 ms 8096 KB Output is correct
9 Correct 221 ms 8292 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2760 KB Output is correct
2 Correct 16 ms 3488 KB Output is correct
3 Correct 168 ms 7692 KB Output is correct
4 Correct 137 ms 8900 KB Output is correct
5 Correct 141 ms 8892 KB Output is correct
6 Correct 130 ms 8920 KB Output is correct
7 Correct 217 ms 8936 KB Output is correct
8 Correct 176 ms 8908 KB Output is correct
9 Correct 153 ms 8880 KB Output is correct
10 Correct 165 ms 8960 KB Output is correct
11 Correct 179 ms 8240 KB Output is correct
12 Correct 133 ms 8368 KB Output is correct
13 Correct 140 ms 8396 KB Output is correct
14 Correct 223 ms 8140 KB Output is correct
15 Correct 230 ms 8924 KB Output is correct
16 Correct 189 ms 8904 KB Output is correct
17 Correct 210 ms 8412 KB Output is correct
18 Correct 164 ms 8260 KB Output is correct
19 Correct 162 ms 8876 KB Output is correct
20 Correct 174 ms 8332 KB Output is correct
21 Correct 116 ms 10008 KB Output is correct
22 Correct 207 ms 10048 KB Output is correct
23 Correct 141 ms 9384 KB Output is correct
24 Correct 219 ms 9372 KB Output is correct
25 Correct 199 ms 8592 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3400 KB Output is correct
2 Correct 30 ms 3568 KB Output is correct
3 Correct 282 ms 9260 KB Output is correct
4 Correct 246 ms 9840 KB Output is correct
5 Correct 197 ms 11004 KB Output is correct
6 Correct 210 ms 10724 KB Output is correct
7 Correct 206 ms 10864 KB Output is correct
8 Correct 208 ms 10812 KB Output is correct
9 Correct 162 ms 8812 KB Output is correct
10 Correct 164 ms 9300 KB Output is correct
11 Correct 156 ms 9764 KB Output is correct
12 Correct 201 ms 10428 KB Output is correct
13 Correct 214 ms 10672 KB Output is correct
14 Correct 212 ms 10756 KB Output is correct
15 Correct 199 ms 10780 KB Output is correct
16 Correct 188 ms 9680 KB Output is correct
17 Correct 130 ms 9776 KB Output is correct
18 Correct 139 ms 9964 KB Output is correct
19 Correct 125 ms 9964 KB Output is correct
20 Correct 144 ms 9888 KB Output is correct
21 Correct 206 ms 10840 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3384 KB Output is correct
2 Correct 17 ms 3568 KB Output is correct
3 Correct 160 ms 9300 KB Output is correct
4 Correct 175 ms 9544 KB Output is correct
5 Correct 181 ms 9712 KB Output is correct
6 Correct 215 ms 10768 KB Output is correct
7 Correct 154 ms 9244 KB Output is correct
8 Correct 173 ms 9580 KB Output is correct
9 Correct 177 ms 9848 KB Output is correct
10 Correct 279 ms 10692 KB Output is correct
11 Correct 210 ms 10816 KB Output is correct
12 Correct 198 ms 10928 KB Output is correct
13 Correct 168 ms 9728 KB Output is correct
14 Correct 159 ms 9268 KB Output is correct
15 Correct 164 ms 9660 KB Output is correct
16 Correct 157 ms 9260 KB Output is correct
17 Correct 168 ms 9660 KB Output is correct
18 Correct 162 ms 9312 KB Output is correct
19 Correct 195 ms 10400 KB Output is correct
20 Correct 203 ms 10788 KB Output is correct
21 Correct 206 ms 10752 KB Output is correct
22 Correct 215 ms 10708 KB Output is correct
23 Correct 209 ms 10668 KB Output is correct
24 Correct 210 ms 10772 KB Output is correct
25 Correct 218 ms 10952 KB Output is correct
26 Correct 213 ms 10916 KB Output is correct
27 Correct 137 ms 9884 KB Output is correct
28 Correct 132 ms 9796 KB Output is correct
29 Correct 135 ms 10052 KB Output is correct
30 Correct 128 ms 9768 KB Output is correct
31 Correct 147 ms 9924 KB Output is correct
32 Correct 144 ms 9832 KB Output is correct
33 Correct 131 ms 10064 KB Output is correct
34 Correct 126 ms 9900 KB Output is correct
35 Correct 138 ms 9848 KB Output is correct
36 Correct 130 ms 9836 KB Output is correct
37 Correct 144 ms 10012 KB Output is correct
38 Correct 140 ms 9800 KB Output is correct
39 Correct 198 ms 10728 KB Output is correct
40 Correct 192 ms 10864 KB Output is correct
41 Correct 190 ms 10652 KB Output is correct
42 Correct 194 ms 10628 KB Output is correct