oj.uz

Submission #106566

# Submission time Handle Problem Language Result Execution time Memory
106566 2019-04-19T06:21:12 Z tictaccat Highway Tolls (IOI18_highway) C++14
12 / 100
 206 ms 7812 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N,A,B,M,depthT;
vector<vector<pair<int,int>>> adj;
vector<pair<int,int>> pos;

void dfs(int u, int depth, int p) {
//  cout << u << " " << pos.size() << "\n";
  for (auto e: adj[u]) {
    int v,k; tie(v,k) = e;
    if (v == p) continue;
    if (depth+1 == depthT) pos.push_back(e);
    else dfs(v,depth+1,u);
  }
}

void find_pair(int tempN, std::vector<int> U, std::vector<int> V, int tempA, int tempB) {

  N = tempN; A = tempA; B = tempB; M = U.size(); adj.resize(N); 

  for (int i = 0; i < M; i++) {
    adj[U[i]].push_back(make_pair(V[i],i));
    adj[V[i]].push_back(make_pair(U[i],i));
  }

  vector<int> w(M,0);
  depthT = ask(w)/A;

  dfs(0,0,-1);

  while (pos.size() > 1) {
    int mid = pos.size()/2;
    for (int i = 0; i < mid; i++) w[pos[i].second] = 0;
    for (int i = mid; i < pos.size(); i++) w[pos[i].second] = 1;
    if (ask(w) == (ll)depthT*A) {
      pos.erase(pos.begin()+mid,pos.end());
    }
    else {
      pos.erase(pos.begin(),pos.begin()+mid);
    }
  }

  //cout << pos[0].first << "\n";

  answer(0, pos[0].first);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = mid; i < pos.size(); i++) w[pos[i].second] = 1;
                       ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 312 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 288 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 ms 248 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1172 KB Output is correct
3 Correct 143 ms 7812 KB Output is correct
4 Correct 147 ms 7796 KB Output is correct
5 Correct 206 ms 7788 KB Output is correct
6 Correct 149 ms 7744 KB Output is correct
7 Correct 159 ms 7692 KB Output is correct
8 Correct 166 ms 7808 KB Output is correct
9 Correct 139 ms 7612 KB Output is correct
10 Correct 184 ms 7784 KB Output is correct
11 Correct 134 ms 7308 KB Output is correct
12 Correct 154 ms 7660 KB Output is correct
13 Correct 163 ms 7592 KB Output is correct
14 Correct 159 ms 7680 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 948 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 2 ms 376 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 Incorrect 32 ms 2328 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 15 ms 1168 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -