답안 #116496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116496 2019-06-12T15:49:24 Z mirbek01 통행료 (IOI18_highway) C++11
51 / 100
512 ms 262148 KB
# include <bits/stdc++.h>
# include "highway.h"
 
using namespace std;
 
const int maxn = 2e5 + 2;
 
int d[maxn], pr[maxn], used[maxn];
long long len, lenB;
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;
            used[g[v][i].second] = 1;
            dfs(to, v);
      }
}
 
bool cmp(int a, int b){
      return d[a] < d[b];
}
 
int f(int ver, int e){
      vec.clear();
      memset(used, 0, sizeof(used));
      if(ver == Ua[e])
            dfs(ver, Va[e]);
      else
            dfs(ver, Ua[e]);
      pr[ver] = e;
      used[e] = 1;
      int ans, l = 0, r = (int)vec.size() - 1;
      sort(vec.begin(), vec.end(), cmp);
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i <= md; i ++){
                  w[pr[vec[i]]] = 1;
            }
            for(int i = 0; i < Ua.size(); i ++){
                  if(!used[i])
                        w[i] = 1;
            }
            long long ret = ask(w);
            if(ret == lenB)
                  r = md - 1, ans = vec[md];
            else
                  l = md + 1;
      }
      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);
      for(int i = 0; i < w.size(); i ++)
            w[i] = 1;
      lenB = 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));
}

Compilation message

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:47: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:63:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < w.size(); i ++)
                      ~~^~~~~~~~~~
highway.cpp:75: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:57:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:85:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       answer(f(Ua[e], e), f(Va[e], e));
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5800 KB Output is correct
2 Correct 7 ms 5752 KB Output is correct
3 Correct 7 ms 5884 KB Output is correct
4 Correct 7 ms 5796 KB Output is correct
5 Correct 7 ms 5800 KB Output is correct
6 Correct 7 ms 5756 KB Output is correct
7 Correct 7 ms 5800 KB Output is correct
8 Correct 7 ms 5820 KB Output is correct
9 Correct 7 ms 5796 KB Output is correct
10 Correct 6 ms 5800 KB Output is correct
11 Correct 7 ms 5804 KB Output is correct
12 Correct 7 ms 5752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 28 ms 6576 KB Output is correct
3 Correct 240 ms 13244 KB Output is correct
4 Correct 244 ms 13136 KB Output is correct
5 Correct 215 ms 13168 KB Output is correct
6 Correct 258 ms 13176 KB Output is correct
7 Correct 243 ms 13188 KB Output is correct
8 Correct 218 ms 13108 KB Output is correct
9 Correct 193 ms 13336 KB Output is correct
10 Correct 199 ms 13172 KB Output is correct
11 Correct 259 ms 13212 KB Output is correct
12 Correct 282 ms 13828 KB Output is correct
13 Correct 260 ms 13640 KB Output is correct
14 Correct 248 ms 13752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 6892 KB Output is correct
2 Correct 48 ms 8116 KB Output is correct
3 Correct 63 ms 9188 KB Output is correct
4 Correct 183 ms 15028 KB Output is correct
5 Correct 191 ms 15036 KB Output is correct
6 Correct 205 ms 15832 KB Output is correct
7 Correct 159 ms 16672 KB Output is correct
8 Correct 187 ms 15392 KB Output is correct
9 Correct 175 ms 15568 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5984 KB Output is correct
2 Correct 31 ms 6572 KB Output is correct
3 Correct 185 ms 11516 KB Output is correct
4 Correct 184 ms 13196 KB Output is correct
5 Correct 180 ms 13264 KB Output is correct
6 Correct 184 ms 13148 KB Output is correct
7 Correct 183 ms 13224 KB Output is correct
8 Correct 218 ms 13232 KB Output is correct
9 Correct 216 ms 13208 KB Output is correct
10 Correct 205 ms 13232 KB Output is correct
11 Correct 242 ms 13552 KB Output is correct
12 Correct 287 ms 13884 KB Output is correct
13 Correct 255 ms 13644 KB Output is correct
14 Correct 264 ms 13548 KB Output is correct
15 Correct 178 ms 13184 KB Output is correct
16 Correct 212 ms 13304 KB Output is correct
17 Correct 242 ms 13716 KB Output is correct
18 Correct 249 ms 13908 KB Output is correct
19 Correct 191 ms 13236 KB Output is correct
20 Correct 215 ms 14136 KB Output is correct
21 Correct 179 ms 13400 KB Output is correct
22 Correct 160 ms 13404 KB Output is correct
23 Correct 206 ms 13376 KB Output is correct
24 Correct 246 ms 13556 KB Output is correct
25 Correct 256 ms 16332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 512 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 466 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -