Submission #116301

#	Time	Username	Problem	Language	Result	Execution time	Memory
116301		mirbek01	Highway Tolls (IOI18_highway)	C++11	12 / 100	415 ms	262148 KiB

highway

# include <bits/stdc++.h>
# include "highway.h"

using namespace std;

const int N = 2e5 + 2;

int d[N], id[N];
vector < pair <int, int> > g[N];

void dfs(int v, int pr = -1){
      for(int i = 0; i < g[v].size(); i ++){
            int to = g[v][i].first;
            if(to == pr)
                  continue;
            d[to] = d[v] + 1;
            id[to] = g[v][i].second;
            dfs(to, v);
      }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
      vector <int> w(U.size(), 0);
      long long len = ask(w) / A;
      for(int i = 0; i < U.size(); i ++){
            g[U[i]].push_back({V[i], i});
            g[V[i]].push_back({U[i], i});
      }
      dfs(0);
      vector <int> v;
      for(int i = 0; i < N; i ++){
            if(d[i] == len)
                  v.push_back(i);
      }
      int l = 0, r = (int)v.size() - 1, T;
      while(l <= r){
            int md = (l + r) >> 1;
            for(int i = 0; i < w.size(); i ++)
                  w[i] = 0;
            for(int i = l; i <= md; i ++){
                  w[id[v[i]]] = 1;
            }
            long long ret = ask(w);
            if(len * A == ret){
                  l = md + 1;
            } else {
                  r = md - 1, T = md;
            }
      }
      answer(0, v[T]);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:12:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < g[v].size(); i ++){
                      ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < U.size(); i ++){
                      ~~^~~~~~~~~~
highway.cpp:38:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp:50:20: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
       answer(0, v[T]);
                    ^

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