Submission #116303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116303	2019-06-12T05:57:36 Z	mirbek01	Highway Tolls (IOI18_highway)	C++11	18 / 100	433 ms	262148 KB

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

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.0 / 5.0

#	Verdict	Execution time	Memory	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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	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