oj.uz

Submission #1018330

# Submission time Handle Problem Language Result Execution time Memory
1018330 2024-07-09T19:04:03 Z vjudge1 Highway Tolls (IOI18_highway) C++17
12 / 100
 221 ms 262144 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;
using namespace std;
using lli=long long;
void dfs(int x, int p, vector<int> &level, vector<vector<int>> &adj){
  for(int y: adj[x]){
    if(y==p) continue;
    level[y]=level[x]+1;
    dfs(y,x,level,adj);
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  vector<int> level (N);
  level[0]=0;
  vector<vector<int>> adj (N);
  for(int i=0; i<N-1; ++i){
    adj[U[i]].pb(V[i]);
    adj[V[i]].pb(U[i]);
  }
  dfs(0,-1,level,adj);

  vector<vector<int>> arle(N);
  for(int i=0; i<N-1; ++i){
    
    int x=max(level[U[i]], level[V[i]]);

    arle[x].pb(i);

  }
  vector<int> aux (N-1,0);

  lli v=ask(aux);
  lli d=v/A;
//  deb(d);
  vector<lli> val;
  vector<lli> arista;
  for(lli x: arle[d]){
    arista.pb(x);
    if(level[U[x]]==d){
      val.pb(U[x]);
    }    
    else{
      val.pb(V[x]);
    }
  //  deb(arista[val.size()-1]);
//    deb(val[val.size()-1]);
  }
  lli l=0;
  lli r=val.size()-1;
  while(r-l>1){
    lli m=(r+l)/2;
    vector<int> aux (N-1,0);
    for(lli i=0; i<=m; ++i){
      aux[arista[i]]=1;
    }
    v=ask(aux);
    if(v==d*A){
      l=m+1;
    }
    else{
      r=m;
    }
  }
   vector<int> aux2 (N-1,0);
    for(lli i=0; i<=l; ++i){
      aux2[arista[i]]=1;
    }
    v=ask(aux2);
    if(v==d*A){
      l=r;
    }

  answer(0, val[l]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 65 ms 10836 KB Output is correct
4 Correct 65 ms 10852 KB Output is correct
5 Correct 68 ms 10812 KB Output is correct
6 Correct 65 ms 10588 KB Output is correct
7 Correct 67 ms 10728 KB Output is correct
8 Correct 67 ms 10824 KB Output is correct
9 Correct 59 ms 10596 KB Output is correct
10 Correct 71 ms 10784 KB Output is correct
11 Correct 56 ms 12564 KB Output is correct
12 Correct 67 ms 13392 KB Output is correct
13 Correct 66 ms 12656 KB Output is correct
14 Correct 60 ms 11976 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2392 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 344 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 204 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 221 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -