제출 #116487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116487		mirbek01	통행료 (IOI18_highway)	C++11	5 / 100	495 ms	262148 KiB

highway

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

using namespace std;

const int maxn = 2e5 + 2;

int d[maxn], pr[maxn];
long long len;
vector < pair <int, int> > g[maxn];
vector <int> vec, Ua, Va;

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

int f(int ver, int e){
      vec.clear();
      if(ver == Ua[e])
            dfs(ver, Va[e]);
      else
            dfs(ver, Ua[e]);
      pr[ver] = e;
      int l = 0, r = (int)vec.size() - 1, id;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i < vec.size(); i ++){
                  if(d[vec[i]] >= md)
                        w[ pr[vec[i]] ] = 1;
            }
            int ret = ask(w);
            if(ret == len)
                  r = md - 1;
            else
                  l = md + 1, id = md;
      }
      vector <int> vv;
      for(int i = 0; i < vec.size(); i ++){
            if(d[vec[i]] == id)
                  vv.push_back(vec[i]);
      }
      l = 0, r = (int)vv.size() - 1;
      int ans;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = l; i <= md; i ++){
                  w[pr[vv[i]]] = 1;
            }
            long long ret = ask(w);
            if(len == ret)
                  l = md + 1;
            else
                  r = md - 1, ans = vv[md];
      }
      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(len == ret)
                  l = md + 1;
            else
                  r = md - 1, e = md;
      }
      answer(f(Ua[e], e), f(Va[e], e));
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:15:24: 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:36:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < vec.size(); i ++){
                            ~~^~~~~~~~~~~~
highway.cpp:47:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:80:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp: In function 'int f(int, int)':
highway.cpp:65:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~
highway.cpp:48:13: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(d[vec[i]] == id)
             ^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:90:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       answer(f(Ua[e], e), f(Va[e], e));
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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