Submission #421512

#	Time	Username	Problem	Language	Result	Execution time	Memory
421512		Sundavar	Highway Tolls (IOI18_highway)	C++14	12 / 100	3089 ms	8584 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;

struct node{
  vector<pii> to;
  int depth = 0;
  bool was = false;
};
vector<node> graph;
void DFS(int curr){
  graph[curr].was = true;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was)
      graph[a.first].depth = graph[curr].depth +1, DFS(a.first);
  graph[curr].was = false;
}
vector<pii> poss;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  graph.resize(N);
  int M = U.size();
  for(int i = 0; i < M; i++){
    graph[U[i]].to.push_back({V[i],i});
    graph[V[i]].to.push_back({U[i],i});
  }
  DFS(0);
  vector<int> s(M, 0);
  int at = ask(s)/A;
  for(int i = 0; i < N; i++)
    if(graph[i].depth == at-1)
      for(pii& a : graph[i].to) 
        if(graph[a.first].depth == at) poss.push_back(a);
  while(poss.size() > 1){
    s.assign(M, 0);
    for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
    if(ask(s) == (at-1)*A + B) poss.resize(poss.size()/2);
    else{
      vector<pii> uj;
      for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      poss = uj;
    }
  }
  //cout<<0<<" "<<poss[0].first<<"\n";
  answer(0, poss[0].first);

}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
      |                    ~~^~~~~~~~~~~~~~~
highway.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      |                                  ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31