oj.uz

Submission #147192

# Submission time Handle Problem Language Result Execution time Memory
147192 2019-08-28T11:07:59 Z Bodo171 Highway Tolls (IOI18_highway) C++14
69 / 100
 391 ms 12576 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 mx,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]=1;
    for(i=0;i<x;i++)
        q[i]=0;
    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]=1;
  mx=ask(q);
  cate=mx/B;
  for(int p=17;p>=0;p--)
     if(ret+(1<<p)<=m&&dist(ret+(1<<p))==mx)
        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 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2680 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 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 29 ms 3576 KB Output is correct
3 Correct 276 ms 11284 KB Output is correct
4 Correct 272 ms 11332 KB Output is correct
5 Correct 277 ms 11544 KB Output is correct
6 Correct 248 ms 11312 KB Output is correct
7 Correct 255 ms 11380 KB Output is correct
8 Correct 230 ms 11512 KB Output is correct
9 Correct 226 ms 11252 KB Output is correct
10 Correct 270 ms 11464 KB Output is correct
11 Correct 266 ms 11196 KB Output is correct
12 Correct 270 ms 11228 KB Output is correct
13 Correct 257 ms 11276 KB Output is correct
14 Correct 277 ms 11268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3640 KB Output is correct
2 Correct 49 ms 4592 KB Output is correct
3 Correct 70 ms 5560 KB Output is correct
4 Correct 179 ms 10900 KB Output is correct
5 Correct 211 ms 10900 KB Output is correct
6 Correct 206 ms 11316 KB Output is correct
7 Correct 206 ms 11064 KB Output is correct
8 Correct 208 ms 11164 KB Output is correct
9 Correct 213 ms 11056 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 30 ms 3576 KB Output is correct
3 Correct 177 ms 9544 KB Output is correct
4 Correct 244 ms 11280 KB Output is correct
5 Correct 232 ms 11320 KB Output is correct
6 Correct 225 ms 11292 KB Output is correct
7 Correct 221 ms 11200 KB Output is correct
8 Correct 234 ms 11156 KB Output is correct
9 Correct 354 ms 11316 KB Output is correct
10 Correct 258 ms 11320 KB Output is correct
11 Correct 269 ms 11224 KB Output is correct
12 Correct 290 ms 11304 KB Output is correct
13 Correct 258 ms 11296 KB Output is correct
14 Correct 259 ms 11224 KB Output is correct
15 Correct 230 ms 11308 KB Output is correct
16 Correct 232 ms 11312 KB Output is correct
17 Correct 251 ms 11580 KB Output is correct
18 Correct 250 ms 11304 KB Output is correct
19 Correct 234 ms 11400 KB Output is correct
20 Correct 296 ms 11280 KB Output is correct
21 Correct 233 ms 11600 KB Output is correct
22 Correct 217 ms 11476 KB Output is correct
23 Correct 257 ms 11456 KB Output is correct
24 Correct 254 ms 11444 KB Output is correct
25 Correct 265 ms 11380 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3752 KB Output is correct
2 Correct 34 ms 3704 KB Output is correct
3 Correct 294 ms 11616 KB Output is correct
4 Correct 334 ms 12048 KB Output is correct
5 Correct 365 ms 12412 KB Output is correct
6 Correct 355 ms 12408 KB Output is correct
7 Correct 333 ms 12428 KB Output is correct
8 Correct 371 ms 12524 KB Output is correct
9 Correct 285 ms 9080 KB Output is correct
10 Correct 285 ms 9356 KB Output is correct
11 Correct 317 ms 9800 KB Output is correct
12 Correct 346 ms 11436 KB Output is correct
13 Correct 373 ms 12016 KB Output is correct
14 Correct 391 ms 12340 KB Output is correct
15 Correct 329 ms 12316 KB Output is correct
16 Correct 317 ms 10080 KB Output is correct
17 Correct 240 ms 11788 KB Output is correct
18 Correct 246 ms 12060 KB Output is correct
19 Correct 254 ms 11704 KB Output is correct
20 Correct 257 ms 11780 KB Output is correct
21 Correct 340 ms 12576 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3736 KB Output is correct
2 Correct 32 ms 3704 KB Output is correct
3 Correct 303 ms 11464 KB Output is correct
4 Correct 276 ms 11920 KB Output is correct
5 Correct 295 ms 11788 KB Output is correct
6 Incorrect 306 ms 12560 KB Output is incorrect: {s, t} is wrong
7 Halted 0 ms 0 KB -