Submission #116303

#	Time	Username	Problem	Language	Result	Execution time	Memory
116303		mirbek01	Highway Tolls (IOI18_highway)	C++11	18 / 100	433 ms	262148 KiB

highway

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

using namespace std;

const int maxn = 2e5 + 2;

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

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});
      }
      bool ok = 1;
      if(U.size() != N - 1)
            ok = 0;
      else
            for(int i = 0; i < N - 1; i ++){
                  if(U[i] != i || V[i] != i + 1)
                        ok = 0;
            }
      if(ok){
            int l = 0, r = (int)U.size() - 1, rt = -1;
            while(l <= r){
                  int md = (l + r) >> 1;
                  for(int i = 0; i < w.size(); i ++){
                        w[i] = 0;
                  }
                  for(int i = 0; i <= md; i ++)
                        w[i] = 1;
                  long long ret = ask(w);
                  if(len * A != ret)
                        r = md - 1;
                  else
                        l = md + 1, rt = md;
            }
            answer(rt + 1, rt + 1 + len);
      } else {
            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:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(U.size() != N - 1)
          ~~~~~~~~~^~~~~~~~
highway.cpp:41:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int i = 0; i < w.size(); i ++){
                                  ~~^~~~~~~~~~
highway.cpp:63:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int i = 0; i < w.size(); i ++)
                                  ~~^~~~~~~~~~
highway.cpp:75:26: 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: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31