oj.uz

Submission #116302

# Submission time Handle Problem Language Result Execution time Memory
116302 2019-06-12T05:49:02 Z mirbek01 Highway Tolls (IOI18_highway) C++11
12 / 100
 409 ms 262148 KB 
# include <bits/stdc++.h>
# include "highway.h"

using namespace std;

const int N = 2e5 + 2;

int d[N], id[N];
vector < pair <int, int> > g[N];

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, ret = -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, ret = md;
            }
            answer(ret + 1, ret + 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 5108 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5108 KB Output is correct
4 Correct 6 ms 5020 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 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 5020 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 20 ms 5644 KB Output is correct
3 Correct 181 ms 10968 KB Output is correct
4 Correct 171 ms 10972 KB Output is correct
5 Correct 176 ms 10976 KB Output is correct
6 Correct 138 ms 10908 KB Output is correct
7 Correct 183 ms 10928 KB Output is correct
8 Correct 178 ms 10980 KB Output is correct
9 Correct 192 ms 10888 KB Output is correct
10 Correct 155 ms 10992 KB Output is correct
11 Correct 153 ms 11332 KB Output is correct
12 Correct 169 ms 11732 KB Output is correct
13 Correct 173 ms 11356 KB Output is correct
14 Correct 165 ms 10900 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 5496 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 409 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 364 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -