답안 #116303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116303 2019-06-12T05:57:36 Z mirbek01 통행료 (IOI18_highway) C++11
18 / 100
433 ms 262148 KB
# 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

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]);
                          ^
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4904 KB Output is correct
2 Correct 6 ms 5016 KB Output is correct
3 Correct 6 ms 5020 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5016 KB Output is correct
7 Correct 6 ms 5016 KB Output is correct
8 Correct 6 ms 5020 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 4932 KB Output is correct
11 Correct 6 ms 5016 KB Output is correct
12 Correct 6 ms 5024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 23 ms 5628 KB Output is correct
3 Correct 160 ms 10980 KB Output is correct
4 Correct 176 ms 11032 KB Output is correct
5 Correct 185 ms 10972 KB Output is correct
6 Correct 151 ms 10900 KB Output is correct
7 Correct 203 ms 10928 KB Output is correct
8 Correct 181 ms 10980 KB Output is correct
9 Correct 162 ms 10884 KB Output is correct
10 Correct 179 ms 10972 KB Output is correct
11 Correct 140 ms 11228 KB Output is correct
12 Correct 187 ms 11876 KB Output is correct
13 Correct 176 ms 11424 KB Output is correct
14 Correct 183 ms 10972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 5416 KB Output is correct
2 Correct 31 ms 5932 KB Output is correct
3 Correct 50 ms 6532 KB Output is correct
4 Correct 159 ms 9600 KB Output is correct
5 Correct 130 ms 9724 KB Output is correct
6 Correct 151 ms 9608 KB Output is correct
7 Correct 174 ms 9608 KB Output is correct
8 Correct 159 ms 9604 KB Output is correct
9 Correct 140 ms 9612 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5036 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 433 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 371 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -