oj.uz

Submission #463708

# Submission time Handle Problem Language Result Execution time Memory
463708 2021-08-11T14:41:51 Z oscar1f Highway Tolls (IOI18_highway) C++17
12 / 100
 165 ms 9876 KB 
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;

//#define int long long

const int MAX_SOM=90*1000;
int nbSom,bas,haut,nbAre,distTotal,petit,grand,mid,rep;
vector<int> deb,fin,quest;
vector<pair<int,int>> bonneDist;
vector<pair<int,int>> adja[MAX_SOM];
int dv[MAX_SOM];

void DFS(int pos,int dist,int anc) {
  if (dv[pos]==0) {
    dv[pos]=1;
    if (dist*bas==distTotal) {
      bonneDist.push_back(make_pair(pos,anc));
    }
    for (int i=0;i<adja[pos].size();i++) {
      DFS(adja[pos][i].first,dist+1,adja[pos][i].second);
    }
  }
}

void find_pair(int N,vector<int> U,vector<int> V,int A,int B) {
  nbAre=U.size();
  nbSom=N;
  deb=U;
  fin=V;
  bas=A;
  haut=B;
  for (int i=0;i<nbAre;i++) {
    quest.push_back(0);
  }
  distTotal=ask(quest);
  for (int i=0;i<nbAre;i++) {
    adja[deb[i]].push_back(make_pair(fin[i],i));
    adja[fin[i]].push_back(make_pair(deb[i],i));
  }
  DFS(0,0,0);
  petit=0;
  grand=bonneDist.size()-1;
  while(petit!=grand) {
    mid=(petit+grand)/2;
    for (int i=petit;i<=mid;i++) {
      quest[bonneDist[i].second]=1;
    }
    rep=ask(quest);
    for (int i=petit;i<=mid;i++) {
      quest[bonneDist[i].second]=0;
    }
    if (rep>distTotal) {
      grand=mid;
    }
    else {
      petit=mid+1;
    }
  }
  answer(0,bonneDist[petit].first);
}

Compilation message

highway.cpp: In function 'void DFS(int, int, int)':
highway.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0;i<adja[pos].size();i++) {
      |                  ~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2376 KB Output is correct
2 Correct 12 ms 3016 KB Output is correct
3 Correct 106 ms 8832 KB Output is correct
4 Correct 152 ms 8788 KB Output is correct
5 Correct 117 ms 8796 KB Output is correct
6 Correct 110 ms 8648 KB Output is correct
7 Correct 158 ms 8712 KB Output is correct
8 Correct 123 ms 8776 KB Output is correct
9 Correct 113 ms 8592 KB Output is correct
10 Correct 165 ms 8728 KB Output is correct
11 Correct 150 ms 9400 KB Output is correct
12 Correct 161 ms 9876 KB Output is correct
13 Correct 117 ms 9496 KB Output is correct
14 Correct 158 ms 9028 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3648 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 2 ms 2376 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 Incorrect 16 ms 3148 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 18 ms 3200 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -