oj.uz

Submission #116301

# Submission time Handle Problem Language Result Execution time Memory
116301 2019-06-12T05:38:02 Z mirbek01 Highway Tolls (IOI18_highway) C++11
12 / 100
 415 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});
      }
      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:38:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp:50:20: 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 5112 KB Output is correct
2 Correct 6 ms 5032 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4908 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 6 ms 5020 KB Output is correct
8 Correct 6 ms 5100 KB Output is correct
9 Correct 6 ms 4984 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 8 ms 5048 KB Output is correct
2 Correct 45 ms 5604 KB Output is correct
3 Correct 175 ms 10980 KB Output is correct
4 Correct 162 ms 10972 KB Output is correct
5 Correct 165 ms 10976 KB Output is correct
6 Correct 169 ms 10896 KB Output is correct
7 Correct 173 ms 10844 KB Output is correct
8 Correct 183 ms 10976 KB Output is correct
9 Correct 171 ms 10844 KB Output is correct
10 Correct 180 ms 10996 KB Output is correct
11 Correct 160 ms 11292 KB Output is correct
12 Correct 188 ms 11740 KB Output is correct
13 Correct 169 ms 11428 KB Output is correct
14 Correct 180 ms 11020 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5984 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 7 ms 5040 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 415 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 374 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -