oj.uz

Submission #147369

# Submission time Handle Problem Language Result Execution time Memory
147369 2019-08-29T10:22:45 Z Bodo171 Highway Tolls (IOI18_highway) C++14
100 / 100
 379 ms 12652 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=100005;
const int mmax=130005;
int n,m,i,p,u,ret;
long long mn,cate,A,B;
int unu[mmax],doi[mmax];
bool always[mmax];
bool inA[nmax],inB[nmax];
int in[nmax],bun[nmax];
int qu[2][nmax],d[2][nmax];
vector<int> v[nmax];
vector<int> q;
long long dist(int x)
{
    for(i=0;i<m;i++)
        q[i]=0;
    for(i=0;i<x;i++)
        q[i]=1;
    return ask(q);
}
void bfs(int x,int wh)
{
    int nod;
    u=1;
    qu[wh][u]=x;d[wh][x]=1;
    for(p=1;p<=u;p++)
    {
        x=qu[wh][p];
        for(i=0;i<v[x].size();i++)
        {
            nod=v[x][i];
            if(!d[wh][nod])
            {
                d[wh][nod]=d[wh][x]+1;
                qu[wh][++u]=nod;
            }
        }
    }
}
int cb(vector<int> mult)
{
    int ans=0;
    for(i=0;i<n;i++)
        in[i]=0;
    for(i=0;i<mult.size();i++)
        in[mult[i]]=1;
    for(int p=17;p>=0;p--)
        if(ans+(1<<p)<=mult.size())
    {
        ans+=(1<<p);
        for(i=0;i<m;i++)
          if(always[i]) q[i]=0;
          else q[i]=1;
        q[ret]=0;
        for(i=0;i<n;i++)
            bun[i]=0;
        for(i=0;i<ans;i++)
            bun[mult[i]]=1;
        for(i=0;i<m;i++)
            if(bun[unu[i]]&&bun[doi[i]])
               q[i]=0;
        long long cat=ask(q);
        if(cat==1LL*cate*A) ans-=(1<<p);
    }
    return mult[ans];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int Aa, int Bb) {
  n=N;m = U.size();
  q.resize(m);
  A=Aa;B=Bb;
  for(i=0;i<m;i++)
  {
      v[U[i]].push_back(V[i]);
      v[V[i]].push_back(U[i]);
      unu[i]=U[i];doi[i]=V[i];
  }
  for(i=0;i<m;i++)
    q[i]=0;
  mn=ask(q);
  cate=mn/A;
  for(int p=17;p>=0;p--)
     if(ret+(1<<p)<=m&&dist(ret+(1<<p))==mn)
            ret+=(1<<p);
   int a=U[ret],b=V[ret];
   bfs(a,0);bfs(b,1);
   vector<int> multA,multB;
   for(i=1;i<=n;i++)
   {
        int nod=qu[0][i];
        if(d[0][nod]<d[1][nod])
        {
            multA.push_back(nod);
            inA[nod]=1;
        }
        nod=qu[1][i];
        if(d[1][nod]<d[0][nod])
        {
            multB.push_back(nod);
            inB[nod]=1;
        }
   }
   for(i=0;i<m;i++)
    if(inB[U[i]]&&inB[V[i]])
       always[i]=1;
   int x=cb(multA);
   for(i=0;i<m;i++)
    always[i]=0;
   for(i=0;i<m;i++)
     if(inA[U[i]]&&inA[V[i]])
       always[i]=1;
   int y=cb(multB);
   answer(x,y);
}

Compilation message

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
highway.cpp: In function 'int cb(std::vector<int>)':
highway.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<mult.size();i++)
             ~^~~~~~~~~~~~
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ans+(1<<p)<=mult.size())
            ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2596 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 4 ms 2676 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2600 KB Output is correct
12 Correct 4 ms 2684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 22 ms 3704 KB Output is correct
3 Correct 244 ms 11384 KB Output is correct
4 Correct 299 ms 11320 KB Output is correct
5 Correct 248 ms 11444 KB Output is correct
6 Correct 249 ms 11348 KB Output is correct
7 Correct 261 ms 11348 KB Output is correct
8 Correct 243 ms 11404 KB Output is correct
9 Correct 232 ms 11272 KB Output is correct
10 Correct 242 ms 11320 KB Output is correct
11 Correct 258 ms 11080 KB Output is correct
12 Correct 273 ms 11192 KB Output is correct
13 Correct 253 ms 11272 KB Output is correct
14 Correct 269 ms 11264 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3648 KB Output is correct
2 Correct 50 ms 4592 KB Output is correct
3 Correct 75 ms 5556 KB Output is correct
4 Correct 211 ms 10916 KB Output is correct
5 Correct 213 ms 10876 KB Output is correct
6 Correct 192 ms 11152 KB Output is correct
7 Correct 173 ms 11072 KB Output is correct
8 Correct 198 ms 11140 KB Output is correct
9 Correct 164 ms 11116 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2728 KB Output is correct
2 Correct 29 ms 3720 KB Output is correct
3 Correct 160 ms 9424 KB Output is correct
4 Correct 235 ms 11284 KB Output is correct
5 Correct 204 ms 11428 KB Output is correct
6 Correct 221 ms 11256 KB Output is correct
7 Correct 220 ms 11212 KB Output is correct
8 Correct 242 ms 11192 KB Output is correct
9 Correct 270 ms 11316 KB Output is correct
10 Correct 255 ms 11312 KB Output is correct
11 Correct 262 ms 11332 KB Output is correct
12 Correct 272 ms 11288 KB Output is correct
13 Correct 293 ms 11396 KB Output is correct
14 Correct 282 ms 11220 KB Output is correct
15 Correct 203 ms 11460 KB Output is correct
16 Correct 192 ms 11432 KB Output is correct
17 Correct 294 ms 11348 KB Output is correct
18 Correct 249 ms 11256 KB Output is correct
19 Correct 224 ms 11188 KB Output is correct
20 Correct 245 ms 11180 KB Output is correct
21 Correct 219 ms 11500 KB Output is correct
22 Correct 179 ms 11404 KB Output is correct
23 Correct 248 ms 11356 KB Output is correct
24 Correct 260 ms 11388 KB Output is correct
25 Correct 269 ms 11276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3704 KB Output is correct
2 Correct 32 ms 3724 KB Output is correct
3 Correct 289 ms 11704 KB Output is correct
4 Correct 326 ms 11856 KB Output is correct
5 Correct 362 ms 12580 KB Output is correct
6 Correct 360 ms 12544 KB Output is correct
7 Correct 347 ms 12520 KB Output is correct
8 Correct 370 ms 12520 KB Output is correct
9 Correct 293 ms 9168 KB Output is correct
10 Correct 287 ms 9356 KB Output is correct
11 Correct 317 ms 9792 KB Output is correct
12 Correct 356 ms 11544 KB Output is correct
13 Correct 338 ms 12148 KB Output is correct
14 Correct 350 ms 12372 KB Output is correct
15 Correct 356 ms 12292 KB Output is correct
16 Correct 325 ms 10124 KB Output is correct
17 Correct 252 ms 11704 KB Output is correct
18 Correct 246 ms 11788 KB Output is correct
19 Correct 237 ms 11708 KB Output is correct
20 Correct 255 ms 11792 KB Output is correct
21 Correct 354 ms 12540 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3624 KB Output is correct
2 Correct 33 ms 3744 KB Output is correct
3 Correct 286 ms 11468 KB Output is correct
4 Correct 302 ms 11616 KB Output is correct
5 Correct 291 ms 11872 KB Output is correct
6 Correct 379 ms 12528 KB Output is correct
7 Correct 200 ms 11664 KB Output is correct
8 Correct 259 ms 11732 KB Output is correct
9 Correct 299 ms 11700 KB Output is correct
10 Correct 317 ms 12420 KB Output is correct
11 Correct 336 ms 12304 KB Output is correct
12 Correct 351 ms 12324 KB Output is correct
13 Correct 278 ms 9960 KB Output is correct
14 Correct 277 ms 9288 KB Output is correct
15 Correct 277 ms 9916 KB Output is correct
16 Correct 284 ms 9324 KB Output is correct
17 Correct 313 ms 9892 KB Output is correct
18 Correct 315 ms 9488 KB Output is correct
19 Correct 349 ms 11292 KB Output is correct
20 Correct 314 ms 11916 KB Output is correct
21 Correct 379 ms 12368 KB Output is correct
22 Correct 368 ms 12344 KB Output is correct
23 Correct 359 ms 12292 KB Output is correct
24 Correct 361 ms 12400 KB Output is correct
25 Correct 367 ms 12420 KB Output is correct
26 Correct 337 ms 12436 KB Output is correct
27 Correct 239 ms 11780 KB Output is correct
28 Correct 232 ms 11664 KB Output is correct
29 Correct 239 ms 11744 KB Output is correct
30 Correct 222 ms 11688 KB Output is correct
31 Correct 256 ms 11836 KB Output is correct
32 Correct 260 ms 11652 KB Output is correct
33 Correct 246 ms 11988 KB Output is correct
34 Correct 249 ms 11688 KB Output is correct
35 Correct 211 ms 11644 KB Output is correct
36 Correct 249 ms 11752 KB Output is correct
37 Correct 259 ms 12048 KB Output is correct
38 Correct 240 ms 11780 KB Output is correct
39 Correct 364 ms 12652 KB Output is correct
40 Correct 346 ms 12556 KB Output is correct
41 Correct 334 ms 12568 KB Output is correct
42 Correct 352 ms 12408 KB Output is correct