oj.uz

Submission #1095873

# Submission time Handle Problem Language Result Execution time Memory
1095873 2024-10-03T10:58:36 Z owoovo Highway Tolls (IOI18_highway) C++17
12 / 100
 249 ms 262144 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define F first 
#define S second 
using namespace std;
vector<pair<int,int>> e[90010];
vector<int> w;
int n,dp[90010],toe[90010];
void dfs(int now,int last){
  dp[now]=dp[last]+1;
  for(auto x:e[now]){
    if(x.F==last)continue;
    toe[x.F]=x.S;
    dfs(x.F,now);
  }
  return;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  w.resize(M);
  for(auto x:w)x=0;
  for(int i=0;i<M;i++){
    e[U[i]].push_back({V[i],i});
    e[V[i]].push_back({U[i],i});
  }
  dp[0]=-1;
  dfs(0,0);
  ll now=ask(w);
  ll need=now/A;
  vector<int> may;
  for(int i=0;i<N;i++){
    if(dp[i]==need)may.push_back(i);
  }
  int l=0,r=may.size();
  while(l<r-1){
    int m=(l+r)>>1;
    //cout<<l<<" "<<r<<" "<<m<<"\n";
    for(int i=0;i<M;i++)w[i]=0;
    for(int i=l;i<m;i++){
      w[toe[may[i]]]=1;
    }
    ll ne=ask(w);
    if(ne!=now){
      r=m;
    }else{
      l=m;
    }
  }
  //cout<<may[l]<<"\n";
  answer(0, may[l]);
  return;
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:22:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   22 |   for(auto x:w)x=0;
      |            ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 8 ms 3160 KB Output is correct
3 Correct 69 ms 8496 KB Output is correct
4 Correct 73 ms 8372 KB Output is correct
5 Correct 66 ms 8272 KB Output is correct
6 Correct 67 ms 8272 KB Output is correct
7 Correct 63 ms 8360 KB Output is correct
8 Correct 63 ms 8484 KB Output is correct
9 Correct 67 ms 8360 KB Output is correct
10 Correct 66 ms 8528 KB Output is correct
11 Correct 76 ms 8780 KB Output is correct
12 Correct 77 ms 9124 KB Output is correct
13 Correct 65 ms 8876 KB Output is correct
14 Correct 65 ms 8528 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -