Submission #117153

#	Time	Username	Problem	Language	Result	Execution time	Memory
117153		mirbek01	Highway Tolls (IOI18_highway)	C++11	100 / 100	420 ms	15444 KiB

highway

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

using namespace std;

const int maxn = 2e5 + 2;

long long len;
int used[maxn], mark[maxn];
vector < pair <int, int> > g[maxn], t[2];
vector <int> Ua, Va;

int f(int v, int tp){
      int l = 0, r = (int)t[tp].size() - 1, ans;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = md; i < t[tp].size(); i ++)
                  w[ t[tp][i].second ] = 1;
            for(int i = 0; i < Ua.size(); i ++){
                  if(!mark[i])
                        w[i] = 1;
            }
            long long ret = ask(w);
            if(ret == len)
                  r = md - 1;
            else
                  l = md + 1, ans = t[tp][md].first;
      }
      return ans;
}

void find_pair(int N, vector<int> AB, vector<int> BA, int A, int B) {
      Ua = AB;
      Va = BA;
      for(int i = 0; i < Ua.size(); i ++){
            g[Ua[i]].push_back({Va[i], i});
            g[Va[i]].push_back({Ua[i], i});
      }

      vector <int> w(Ua.size(), 0);
      len = ask(w);

      int l = 0, r = (int)Ua.size() - 1, e;

      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(ret == len)
                  l = md + 1;
            else
                  r = md - 1, e = md;
      }

      mark[e] = 1;

      queue <pair <int, int> > q;
      q.push({Ua[e], 0});
      q.push({Va[e], 1});
      used[Ua[e]] = used[Va[e]] = 1;
      t[0].push_back({Ua[e], e});
      t[1].push_back({Va[e], e});

      while(!q.empty()){
            int v = q.front().first, tp = q.front().second;
            q.pop();
            for(int i = 0; i < g[v].size(); i ++){
                  int to = g[v][i].first, id = g[v][i].second;
                  if(used[to])
                        continue;
                  mark[id] = 1;
                  used[to] = 1;
                  t[tp].push_back({to, id});
                  q.push({to, tp});
            }
      }

      answer(f(Ua[e], 0), f(Va[e], 1));
}

Compilation message (stderr)

highway.cpp: In function 'int f(int, int)':
highway.cpp:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = md; i < t[tp].size(); i ++)
                             ~~^~~~~~~~~~~~~~
highway.cpp:20:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < Ua.size(); i ++){
                            ~~^~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:48:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp:71:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < g[v].size(); i ++){
                            ~~^~~~~~~~~~~~~
highway.cpp: In function 'int f(int, int)':
highway.cpp:30:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~

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