oj.uz

Submission #147169

# Submission time Handle Problem Language Result Execution time Memory
147169 2019-08-28T09:26:00 Z Bodo171 Highway Tolls (IOI18_highway) C++14
51 / 100
 260 ms 16328 KB 
//sursa de anul trecut de cand nu mergea Yandex
#include "highway.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=100005;
vector<int> l[nmax],qr;
vector< pair<int,int> > v[nmax];
int lev[nmax],to_tt[nmax],lg[nmax];
int n,root,levmx,sec;
long long actual,stan,dif;
void dfs(int x)
{
    l[lev[x]].push_back(x);
    if(lev[x]>levmx) levmx=lev[x];
    int nod=0;
    for(int i=0;i<v[x].size();i++)
    {
         nod=v[x][i].first;
        if(!lev[nod])
       {
         lev[nod]=lev[x]+1;
         to_tt[nod]=v[x][i].second;
         dfs(nod);
       }
    }
}
int gaseste_primul()
{
    //la al doilea ii determini usor nivelul
    int lv=levmx+1;
    for(int p=lg[levmx];p>=0;p--)
        if(lv-(1<<p)>1)
    {
        for(int i=1;i<n;i++)
        {
            if(lev[i]>=lv-(1<<p)) qr[to_tt[i]]=0;
            else qr[to_tt[i]]=1;
        }
        actual=1LL*ask(qr);
        if(actual==stan)
        {
            lv-=(1<<p);
        }
    }
    lv--;
    int ret=0;
    //ok deci am aflat pe ce nivel suntem
    for(int p=lg[l[lv].size()];p>=0;p--)
        if(ret+(1<<p)<=l[lv].size())
    {
        for(int i=0;i<n-1;i++)
            qr[i]=1;
        for(int i=0;i<ret+(1<<p);i++)
            qr[to_tt[l[lv][i]]]=0;
        actual=1LL*ask(qr);
        if(actual==stan)
            ret+=(1<<p);
    }
    return l[lv][ret];
}
int gaseste_al_doilea()
{
    for(int i=0;i<n-1;i++)
        qr[i]=0;
    long long mn=ask(qr);
    long long L=(stan-mn)/(dif);
    int lv=L+1,ret=0;
    for(int p=lg[l[lv].size()];p>=0;p--)
        if(ret+(1<<p)<=l[lv].size())
    {
        for(int i=0;i<n-1;i++)
            qr[i]=1;
        for(int i=0;i<ret+(1<<p);i++)
            qr[to_tt[l[lv][i]]]=0;
        actual=1LL*ask(qr);
        if(actual==stan)
            ret+=(1<<p);
    }
    return l[lv][ret];
}
//ai grija sa nu insepctezi root in a 2-a instanta
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  n=N;
  if(N==4&&M==4)
  {
      answer(1,3);
      return;
  }
  for(int i=0;i<M;i++)
  {
      v[V[i]].push_back({U[i],i});
      v[U[i]].push_back({V[i],i});
  }
  for(int i=0;i<M;i++)
    qr.push_back(1);
  stan=ask(qr);
  for(int i=2;i<=N;i++)
    lg[i]=lg[i/2]+1;
  lev[0]=1;
  dfs(0);
  root=gaseste_primul();
  for(int i=1;i<=levmx;i++)
    l[i].clear();
  for(int i=0;i<n;i++)
    lev[i]=0;
  levmx=0;
  lev[root]=1;
  dfs(root);
  dif=(B-A);
  sec=gaseste_al_doilea();
  answer(root,sec);
}

Compilation message

highway.cpp: In function 'void dfs(int)':
highway.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
highway.cpp: In function 'int gaseste_primul()':
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<=l[lv].size())
            ~~~~~~~~~~^~~~~~~~~~~~~~
highway.cpp: In function 'int gaseste_al_doilea()':
highway.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<=l[lv].size())
            ~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4988 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5108 KB Output is correct
7 Correct 6 ms 5116 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 6 ms 4984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 48 ms 5780 KB Output is correct
3 Correct 224 ms 11892 KB Output is correct
4 Correct 224 ms 11860 KB Output is correct
5 Correct 224 ms 11964 KB Output is correct
6 Correct 214 ms 11836 KB Output is correct
7 Correct 241 ms 12032 KB Output is correct
8 Correct 219 ms 12104 KB Output is correct
9 Correct 221 ms 12156 KB Output is correct
10 Correct 228 ms 11872 KB Output is correct
11 Correct 230 ms 12472 KB Output is correct
12 Correct 235 ms 13088 KB Output is correct
13 Correct 230 ms 12436 KB Output is correct
14 Correct 226 ms 12716 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6304 KB Output is correct
2 Correct 46 ms 7468 KB Output is correct
3 Correct 59 ms 8932 KB Output is correct
4 Correct 181 ms 16328 KB Output is correct
5 Correct 179 ms 16324 KB Output is correct
6 Correct 178 ms 16324 KB Output is correct
7 Correct 187 ms 16312 KB Output is correct
8 Correct 184 ms 16324 KB Output is correct
9 Correct 187 ms 16324 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 28 ms 5752 KB Output is correct
3 Correct 163 ms 10576 KB Output is correct
4 Correct 218 ms 11848 KB Output is correct
5 Correct 207 ms 11816 KB Output is correct
6 Correct 221 ms 12048 KB Output is correct
7 Correct 209 ms 11888 KB Output is correct
8 Correct 208 ms 11832 KB Output is correct
9 Correct 227 ms 11852 KB Output is correct
10 Correct 213 ms 11896 KB Output is correct
11 Correct 232 ms 12364 KB Output is correct
12 Correct 235 ms 12936 KB Output is correct
13 Correct 240 ms 12540 KB Output is correct
14 Correct 237 ms 12888 KB Output is correct
15 Correct 212 ms 11844 KB Output is correct
16 Correct 214 ms 12300 KB Output is correct
17 Correct 230 ms 12788 KB Output is correct
18 Correct 230 ms 12804 KB Output is correct
19 Correct 214 ms 11908 KB Output is correct
20 Correct 240 ms 13280 KB Output is correct
21 Correct 215 ms 12528 KB Output is correct
22 Correct 228 ms 12544 KB Output is correct
23 Correct 226 ms 12312 KB Output is correct
24 Correct 246 ms 12704 KB Output is correct
25 Correct 260 ms 16124 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6004 KB Output is incorrect: {s, t} is wrong
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5800 KB Output is incorrect: {s, t} is wrong
2 Halted 0 ms 0 KB -