oj.uz

Submission #117153

# Submission time Handle Problem Language Result Execution time Memory
117153 2019-06-15T03:33:08 Z mirbek01 Highway Tolls (IOI18_highway) C++11
100 / 100
 420 ms 15444 KB 
# include <bits/stdc++.h>
# include "highway.h"

using namespace std;

const int maxn = 2e5 + 2;

long long len;
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 = md; i < t[tp].size(); i ++)
                  w[ t[tp][i].second ] = 1;
            for(int i = 0; i < Ua.size(); i ++){
                  if(!mark[i])
                        w[i] = 1;
            }
            long long ret = ask(w);
            if(ret == len)
                  r = md - 1;
            else
                  l = md + 1, ans = t[tp][md].first;
      }
      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(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:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = md; i < t[tp].size(); i ++)
                             ~~^~~~~~~~~~~~~~
highway.cpp:20: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:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < Ua.size(); i ++){
                      ~~^~~~~~~~~~~
highway.cpp:48:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < w.size(); i ++)
                            ~~^~~~~~~~~~
highway.cpp:71: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:30: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 4984 KB Output is correct
4 Correct 6 ms 4904 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5020 KB Output is correct
8 Correct 6 ms 5024 KB Output is correct
9 Correct 6 ms 5032 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5104 KB Output is correct
12 Correct 6 ms 5104 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 18 ms 5860 KB Output is correct
3 Correct 185 ms 12736 KB Output is correct
4 Correct 214 ms 12784 KB Output is correct
5 Correct 208 ms 12836 KB Output is correct
6 Correct 203 ms 12704 KB Output is correct
7 Correct 220 ms 12744 KB Output is correct
8 Correct 216 ms 12744 KB Output is correct
9 Correct 198 ms 12740 KB Output is correct
10 Correct 199 ms 12744 KB Output is correct
11 Correct 198 ms 12344 KB Output is correct
12 Correct 203 ms 12328 KB Output is correct
13 Correct 202 ms 12204 KB Output is correct
14 Correct 206 ms 12368 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5880 KB Output is correct
2 Correct 42 ms 6648 KB Output is correct
3 Correct 75 ms 7428 KB Output is correct
4 Correct 193 ms 12196 KB Output is correct
5 Correct 182 ms 12236 KB Output is correct
6 Correct 153 ms 12180 KB Output is correct
7 Correct 165 ms 12116 KB Output is correct
8 Correct 167 ms 12100 KB Output is correct
9 Correct 180 ms 12316 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5076 KB Output is correct
2 Correct 29 ms 5880 KB Output is correct
3 Correct 145 ms 11308 KB Output is correct
4 Correct 215 ms 12684 KB Output is correct
5 Correct 217 ms 12692 KB Output is correct
6 Correct 201 ms 12692 KB Output is correct
7 Correct 194 ms 12780 KB Output is correct
8 Correct 205 ms 12680 KB Output is correct
9 Correct 204 ms 12776 KB Output is correct
10 Correct 220 ms 12840 KB Output is correct
11 Correct 215 ms 12144 KB Output is correct
12 Correct 205 ms 12276 KB Output is correct
13 Correct 212 ms 12504 KB Output is correct
14 Correct 205 ms 12240 KB Output is correct
15 Correct 181 ms 12736 KB Output is correct
16 Correct 172 ms 12744 KB Output is correct
17 Correct 200 ms 12228 KB Output is correct
18 Correct 194 ms 12268 KB Output is correct
19 Correct 220 ms 12732 KB Output is correct
20 Correct 184 ms 12156 KB Output is correct
21 Correct 171 ms 13496 KB Output is correct
22 Correct 167 ms 13452 KB Output is correct
23 Correct 200 ms 13316 KB Output is correct
24 Correct 189 ms 13032 KB Output is correct
25 Correct 211 ms 12392 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5968 KB Output is correct
2 Correct 53 ms 6000 KB Output is correct
3 Correct 227 ms 13348 KB Output is correct
4 Correct 267 ms 13952 KB Output is correct
5 Correct 304 ms 15380 KB Output is correct
6 Correct 302 ms 15212 KB Output is correct
7 Correct 313 ms 15204 KB Output is correct
8 Correct 363 ms 15212 KB Output is correct
9 Correct 271 ms 13136 KB Output is correct
10 Correct 275 ms 13540 KB Output is correct
11 Correct 279 ms 14016 KB Output is correct
12 Correct 333 ms 14908 KB Output is correct
13 Correct 312 ms 15068 KB Output is correct
14 Correct 317 ms 15312 KB Output is correct
15 Correct 286 ms 15280 KB Output is correct
16 Correct 286 ms 14296 KB Output is correct
17 Correct 200 ms 13384 KB Output is correct
18 Correct 167 ms 13532 KB Output is correct
19 Correct 194 ms 13408 KB Output is correct
20 Correct 184 ms 13508 KB Output is correct
21 Correct 298 ms 15144 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5968 KB Output is correct
2 Correct 32 ms 6064 KB Output is correct
3 Correct 234 ms 13368 KB Output is correct
4 Correct 261 ms 13652 KB Output is correct
5 Correct 277 ms 14144 KB Output is correct
6 Correct 314 ms 15228 KB Output is correct
7 Correct 230 ms 13308 KB Output is correct
8 Correct 235 ms 13664 KB Output is correct
9 Correct 272 ms 13948 KB Output is correct
10 Correct 328 ms 15304 KB Output is correct
11 Correct 324 ms 15248 KB Output is correct
12 Correct 316 ms 15200 KB Output is correct
13 Correct 274 ms 14020 KB Output is correct
14 Correct 234 ms 13576 KB Output is correct
15 Correct 250 ms 14132 KB Output is correct
16 Correct 247 ms 13600 KB Output is correct
17 Correct 222 ms 14148 KB Output is correct
18 Correct 258 ms 13668 KB Output is correct
19 Correct 303 ms 14864 KB Output is correct
20 Correct 309 ms 15164 KB Output is correct
21 Correct 349 ms 15280 KB Output is correct
22 Correct 323 ms 15192 KB Output is correct
23 Correct 251 ms 15188 KB Output is correct
24 Correct 324 ms 15204 KB Output is correct
25 Correct 420 ms 15388 KB Output is correct
26 Correct 292 ms 15444 KB Output is correct
27 Correct 201 ms 13528 KB Output is correct
28 Correct 155 ms 13324 KB Output is correct
29 Correct 211 ms 13700 KB Output is correct
30 Correct 211 ms 13444 KB Output is correct
31 Correct 204 ms 13516 KB Output is correct
32 Correct 184 ms 13396 KB Output is correct
33 Correct 198 ms 13672 KB Output is correct
34 Correct 187 ms 13480 KB Output is correct
35 Correct 176 ms 13440 KB Output is correct
36 Correct 222 ms 13384 KB Output is correct
37 Correct 210 ms 13740 KB Output is correct
38 Correct 160 ms 13484 KB Output is correct
39 Correct 312 ms 15188 KB Output is correct
40 Correct 311 ms 15080 KB Output is correct
41 Correct 288 ms 15108 KB Output is correct
42 Correct 321 ms 15212 KB Output is correct