oj.uz

Submission #116488

# Submission time Handle Problem Language Result Execution time Memory
116488 2019-06-12T15:16:47 Z mirbek01 Highway Tolls (IOI18_highway) C++11
0 / 100
 504 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);
      }
}

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;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i <= md; i ++){
                  w[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:42: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:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < w.size(); i ++)
                      ~~^~~~~~~~~~
highway.cpp:70: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:52: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:80:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       answer(f(Ua[e], e), f(Va[e], e));
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6896 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 8 ms 5880 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 504 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 458 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -