oj.uz

Submission #116487

# Submission time Handle Problem Language Result Execution time Memory
116487 2019-06-12T15:06:18 Z mirbek01 Highway Tolls (IOI18_highway) C++11
5 / 100
 495 ms 262148 KB 
# include <bits/stdc++.h>
# include "highway.h"

using namespace std;

const int maxn = 2e5 + 2;

int d[maxn], pr[maxn];
long long len;
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;
            dfs(to, v);
      }
}

int f(int ver, int e){
      vec.clear();
      if(ver == Ua[e])
            dfs(ver, Va[e]);
      else
            dfs(ver, Ua[e]);
      pr[ver] = e;
      int l = 0, r = (int)vec.size() - 1, id;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i < vec.size(); i ++){
                  if(d[vec[i]] >= md)
                        w[ pr[vec[i]] ] = 1;
            }
            int ret = ask(w);
            if(ret == len)
                  r = md - 1;
            else
                  l = md + 1, id = md;
      }
      vector <int> vv;
      for(int i = 0; i < vec.size(); i ++){
            if(d[vec[i]] == id)
                  vv.push_back(vec[i]);
      }
      l = 0, r = (int)vv.size() - 1;
      int ans;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = l; i <= md; i ++){
                  w[pr[vv[i]]] = 1;
            }
            long long ret = ask(w);
            if(len == ret)
                  l = md + 1;
            else
                  r = md - 1, ans = vv[md];
      }
      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);
      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:36:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < vec.size(); i ++){
                            ~~^~~~~~~~~~~~
highway.cpp:47:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:80: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:65:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~
highway.cpp:48:13: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(d[vec[i]] == id)
             ^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:90:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       answer(f(Ua[e], e), f(Va[e], e));
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4988 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5028 KB Output is correct
4 Correct 6 ms 5104 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct
10 Correct 7 ms 4984 KB Output is correct
11 Correct 6 ms 5108 KB Output is correct
12 Correct 6 ms 5024 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5128 KB Output is correct
2 Correct 22 ms 5856 KB Output is correct
3 Correct 209 ms 12444 KB Output is correct
4 Incorrect 211 ms 12404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6184 KB Output is correct
2 Correct 45 ms 7316 KB Output is correct
3 Correct 48 ms 8512 KB Output is correct
4 Correct 165 ms 14320 KB Output is correct
5 Correct 183 ms 14256 KB Output is correct
6 Correct 174 ms 15044 KB Output is correct
7 Correct 173 ms 15876 KB Output is correct
8 Correct 162 ms 14596 KB Output is correct
9 Incorrect 195 ms 14720 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5076 KB Output is correct
2 Correct 51 ms 5732 KB Output is correct
3 Correct 158 ms 10744 KB Output is correct
4 Correct 195 ms 12400 KB Output is correct
5 Correct 235 ms 12436 KB Output is correct
6 Correct 205 ms 12368 KB Output is correct
7 Correct 198 ms 12448 KB Output is correct
8 Correct 169 ms 12540 KB Output is correct
9 Incorrect 194 ms 12424 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 495 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 440 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -