oj.uz

Submission #117152

# Submission time Handle Problem Language Result Execution time Memory
117152 2019-06-15T03:30:09 Z mirbek01 Highway Tolls (IOI18_highway) C++11
51 / 100
 230 ms 13504 KB 
# include <bits/stdc++.h>
# include "highway.h"

using namespace std;

const int maxn = 2e5 + 2;

long long len, lenB;
int used[maxn], mark[maxn];
vector < pair <int, int> > g[maxn], t[2];
vector <int> Ua, Va;

int f(int v, int tp){
      int l = 0, r = (int)t[tp].size() - 1, ans;
      while(l <= r){
            int md = (l + r) >> 1;
            vector <int> w(Ua.size(), 0);
            for(int i = 0; i <= md; i ++)
                  w[ t[tp][i].second ] = 1;
            for(int i = 0; i < Ua.size(); i ++){
                  if(!mark[i])
                        w[i] = 1;
            }
            for(int i = 0; i < t[tp ^ 1].size(); i ++)
                  w[ t[tp ^ 1][i].second ] = 1;
            long long ret = ask(w);
            if(ret == lenB)
                  r = md - 1, ans = t[tp][md].first;
            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(ret == len)
                  l = md + 1;
            else
                  r = md - 1, e = md;
      }

      mark[e] = 1;

      queue <pair <int, int> > q;
      q.push({Ua[e], 0});
      q.push({Va[e], 1});
      used[Ua[e]] = used[Va[e]] = 1;
      t[0].push_back({Ua[e], e});
      t[1].push_back({Va[e], e});

      while(!q.empty()){
            int v = q.front().first, tp = q.front().second;
            q.pop();
            for(int i = 0; i < g[v].size(); i ++){
                  int to = g[v][i].first, id = g[v][i].second;
                  if(used[to])
                        continue;
                  mark[id] = 1;
                  used[to] = 1;
                  t[tp].push_back({to, id});
                  q.push({to, tp});
            }
      }

      answer(f(Ua[e], 0), f(Va[e], 1));
}

Compilation message

highway.cpp: In function 'int f(int, int)':
highway.cpp:20:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < Ua.size(); i ++){
                            ~~^~~~~~~~~~~
highway.cpp:24:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < t[tp ^ 1].size(); i ++)
                            ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:38:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < w.size(); i ++)
                      ~~^~~~~~~~~~
highway.cpp:53:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp:76:30: 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:32:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       return ans;
              ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 24 ms 5964 KB Output is correct
3 Correct 193 ms 12728 KB Output is correct
4 Correct 210 ms 12828 KB Output is correct
5 Correct 215 ms 12752 KB Output is correct
6 Correct 206 ms 12720 KB Output is correct
7 Correct 203 ms 12812 KB Output is correct
8 Correct 202 ms 12744 KB Output is correct
9 Correct 209 ms 12736 KB Output is correct
10 Correct 194 ms 12748 KB Output is correct
11 Correct 215 ms 12224 KB Output is correct
12 Correct 225 ms 12332 KB Output is correct
13 Correct 218 ms 12116 KB Output is correct
14 Correct 177 ms 12228 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5876 KB Output is correct
2 Correct 42 ms 6648 KB Output is correct
3 Correct 44 ms 7484 KB Output is correct
4 Correct 171 ms 12188 KB Output is correct
5 Correct 180 ms 12164 KB Output is correct
6 Correct 172 ms 12192 KB Output is correct
7 Correct 155 ms 12232 KB Output is correct
8 Correct 180 ms 12128 KB Output is correct
9 Correct 161 ms 12328 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5080 KB Output is correct
2 Correct 29 ms 5800 KB Output is correct
3 Correct 153 ms 11300 KB Output is correct
4 Correct 194 ms 12692 KB Output is correct
5 Correct 199 ms 12760 KB Output is correct
6 Correct 194 ms 12836 KB Output is correct
7 Correct 203 ms 12732 KB Output is correct
8 Correct 203 ms 12800 KB Output is correct
9 Correct 215 ms 12780 KB Output is correct
10 Correct 210 ms 12768 KB Output is correct
11 Correct 210 ms 12148 KB Output is correct
12 Correct 230 ms 12292 KB Output is correct
13 Correct 214 ms 12364 KB Output is correct
14 Correct 219 ms 12168 KB Output is correct
15 Correct 188 ms 12828 KB Output is correct
16 Correct 193 ms 12864 KB Output is correct
17 Correct 230 ms 12248 KB Output is correct
18 Correct 219 ms 12172 KB Output is correct
19 Correct 196 ms 12788 KB Output is correct
20 Correct 214 ms 12160 KB Output is correct
21 Correct 182 ms 13504 KB Output is correct
22 Correct 178 ms 13504 KB Output is correct
23 Correct 182 ms 13324 KB Output is correct
24 Correct 200 ms 13028 KB Output is correct
25 Correct 208 ms 12380 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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