oj.uz

Submission #382394

# Submission time Handle Problem Language Result Execution time Memory
382394 2021-03-27T08:26:35 Z sad Highway Tolls (IOI18_highway) C++14
51 / 100
 170 ms 13376 KB 
#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
long long a,b,n;const int N=90090;
int pa[N],what[N],in[N];long long l;vector<int>vv;vector<pair<int,int>>v[N];
vector<int>w;
void dfs(int x,int p,long long le)
{
    pa[x]=p;
    if(le==0){
        vv.pb(x);return;
    }
    for(auto it:v[x])
    {
        if(it.se==p)continue;
        dfs(it.fi,it.se,le-1);
    }
}
int ch(int ll,int r)
{
    w.clear();
    for(int i=0;i<n-1;i++)w.pb(0);
    for(int i=ll;i<=r;i++)
    {
        w[pa[vv[i]]]=1;
    }
    long long x=ask(w);
    w.clear();
    long long y=a*l;
    if(x>y)return 1;
    return 0;
}
int chee(int ll,int r)
{
    w.clear();
    for(int i=0;i<n-1;i++)w.pb(0);
    for(int i=ll;i<=r;i++)
    {
        w[pa[what[i]]]=1;
    }
    long long x=ask(w);
    w.clear();
    long long y=a*l;
    if(x>y)return 1;
    return 0;
}
int timer=-1;
void go (int x,int p)
{
    pa[x]=p;
    in[x]=++timer;
    what[timer]=x;
    for(auto it:v[x])
    {
        if(it.se==p)continue;
        go(it.fi,it.se);
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  a=A;b=B;
  w.clear();
  n=N;
  for(int i=0;i<n-1;i++)w.pb(0);
  l=ask(w)/a;
  for(int i=0;i<n-1;i++)
  {
      v[V[i]].pb({U[i],i});
      v[U[i]].pb({V[i],i});
  }
  go(0,-1);
  int st=0,end=timer;
  while(st<end)
  {
      int mid=(st+end)/2;
      if(chee(mid+1,end))
      {
          st=mid+1;
      }
      else end=mid;
  }
  int point=what[st];
  dfs(point,-1,l);
  int  m=vv.size();
  st=0,end=m-1;
  while(st<end)
  {
      int mid=st+end;mid/=2;
      if(ch(st,mid)) end=mid;
      else st=mid+1;
  }
  answer(point,vv[st]);
}
/*
4 3
1 2
1 2
1 2
1 0
1 3
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2540 KB Output is correct
2 Correct 15 ms 3180 KB Output is correct
3 Correct 149 ms 8808 KB Output is correct
4 Correct 149 ms 8732 KB Output is correct
5 Correct 152 ms 8796 KB Output is correct
6 Correct 145 ms 8852 KB Output is correct
7 Correct 143 ms 8716 KB Output is correct
8 Correct 132 ms 8804 KB Output is correct
9 Correct 150 ms 8732 KB Output is correct
10 Correct 155 ms 8688 KB Output is correct
11 Correct 142 ms 8820 KB Output is correct
12 Correct 139 ms 9116 KB Output is correct
13 Correct 138 ms 8936 KB Output is correct
14 Correct 170 ms 8880 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3436 KB Output is correct
2 Correct 26 ms 4332 KB Output is correct
3 Correct 36 ms 5228 KB Output is correct
4 Correct 110 ms 10852 KB Output is correct
5 Correct 111 ms 10852 KB Output is correct
6 Correct 96 ms 11724 KB Output is correct
7 Correct 115 ms 10852 KB Output is correct
8 Correct 111 ms 10852 KB Output is correct
9 Correct 102 ms 10980 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2540 KB Output is correct
2 Correct 15 ms 3308 KB Output is correct
3 Correct 104 ms 7328 KB Output is correct
4 Correct 133 ms 8804 KB Output is correct
5 Correct 134 ms 8712 KB Output is correct
6 Correct 134 ms 8716 KB Output is correct
7 Correct 131 ms 8676 KB Output is correct
8 Correct 130 ms 8804 KB Output is correct
9 Correct 142 ms 8840 KB Output is correct
10 Correct 137 ms 8728 KB Output is correct
11 Correct 147 ms 8732 KB Output is correct
12 Correct 148 ms 9512 KB Output is correct
13 Correct 143 ms 8964 KB Output is correct
14 Correct 131 ms 9220 KB Output is correct
15 Correct 137 ms 8804 KB Output is correct
16 Correct 168 ms 8808 KB Output is correct
17 Correct 145 ms 9112 KB Output is correct
18 Correct 149 ms 8920 KB Output is correct
19 Correct 137 ms 8676 KB Output is correct
20 Correct 131 ms 9332 KB Output is correct
21 Correct 135 ms 9680 KB Output is correct
22 Correct 131 ms 9676 KB Output is correct
23 Correct 128 ms 9292 KB Output is correct
24 Correct 136 ms 9812 KB Output is correct
25 Correct 158 ms 13376 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2668 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2668 KB Incorrect
2 Halted 0 ms 0 KB -