oj.uz

Submission #116489

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

using namespace std;

const int maxn = 2e5 + 2;

int d[maxn], pr[maxn], used[maxn];
long long len, lenB;
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;
            used[g[v][i].second] = 1;
            dfs(to, v);
      }
}

bool cmp(int a, int b){
      return d[a] < d[b];
}

int f(int ver, int e){
      vec.clear();
      memset(used, 0, sizeof(used));
      if(ver == Ua[e])
            dfs(ver, Va[e]);
      else
            dfs(ver, Ua[e]);
      pr[ver] = e;
      used[e] = 1;
      int ans, l = 0, r = (int)vec.size() - 1;
      sort(vec.begin(), vec.end(), cmp);
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i <= md; i ++){
                  w[pr[vec[i]]] = 1;
            }
            for(int i = 0; i < Ua.size(); i ++){
                  if(!used[i])
                        w[i] = 1;
            }
            int ret = ask(w);
            if(ret == lenB)
                  r = md - 1, ans = vec[md];
            else
                  l = md + 1;
      }
      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);
      for(int i = 0; i < w.size(); i ++)
            w[i] = 1;
      lenB = 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:47:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < Ua.size(); i ++){
                            ~~^~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:63:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < w.size(); i ++)
                      ~~^~~~~~~~~~
highway.cpp:75: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:57:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:85: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 7 ms 5880 KB Output is correct
2 Correct 7 ms 5800 KB Output is correct
3 Correct 7 ms 5800 KB Output is correct
4 Correct 7 ms 5804 KB Output is correct
5 Correct 7 ms 5800 KB Output is correct
6 Correct 7 ms 5904 KB Output is correct
7 Correct 7 ms 5752 KB Output is correct
8 Correct 7 ms 5796 KB Output is correct
9 Correct 7 ms 5752 KB Output is correct
10 Correct 9 ms 5804 KB Output is correct
11 Correct 7 ms 5800 KB Output is correct
12 Correct 7 ms 5776 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5860 KB Output is correct
2 Correct 23 ms 6636 KB Output is correct
3 Correct 245 ms 13232 KB Output is correct
4 Correct 233 ms 13196 KB Output is correct
5 Correct 214 ms 13172 KB Output is correct
6 Correct 195 ms 13116 KB Output is correct
7 Correct 234 ms 13200 KB Output is correct
8 Correct 232 ms 13172 KB Output is correct
9 Correct 221 ms 13240 KB Output is correct
10 Correct 203 ms 13168 KB Output is correct
11 Correct 201 ms 13184 KB Output is correct
12 Correct 262 ms 13868 KB Output is correct
13 Correct 224 ms 13640 KB Output is correct
14 Incorrect 293 ms 13772 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7032 KB Output is correct
2 Correct 36 ms 8120 KB Output is correct
3 Correct 51 ms 9188 KB Output is correct
4 Correct 165 ms 14996 KB Output is correct
5 Correct 150 ms 15048 KB Output is correct
6 Correct 202 ms 15844 KB Output is correct
7 Correct 176 ms 16680 KB Output is correct
8 Correct 175 ms 15504 KB Output is correct
9 Incorrect 167 ms 15696 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5856 KB Output is correct
2 Correct 29 ms 6592 KB Output is correct
3 Correct 138 ms 11524 KB Output is correct
4 Correct 241 ms 13124 KB Output is correct
5 Correct 170 ms 13240 KB Output is correct
6 Correct 192 ms 13272 KB Output is correct
7 Correct 219 ms 13232 KB Output is correct
8 Correct 208 ms 13220 KB Output is correct
9 Incorrect 251 ms 13236 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 556 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 450 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -