oj.uz

답안 #284030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284030 2020-08-26T13:55:03 Z milleniumEeee 통행료 (IOI18_highway) C++14
0 / 100
 19 ms 3072 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define fr first
#define sc second
using namespace std;

const int N = 90004;
vector <pii> g[N];
int x[N], y[N];
int n, m, a, b;
int S, T;
vector <int> w;

void create(vector <int> &path) {
  for (int i = 0; i < m; i++) {
    w[i] = 0;
  }
  for (int edge : path) {
    w[edge] = 1;
  }
}

void dfs(int v, int par, vector <int> &path) {
  if (v != 0) {
    create(path);
    int dist = ask(w);
    if (dist == szof(path) * b) {
      S = 0, T = v;
    }
  }
  for (pii to : g[v]) {
    if (to.sc != par) {
      path.push_back(to.fr);
      dfs(to.sc, v, path);
      path.pop_back();
    }
  }
}

void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
  n = NN;
  m = U.size();
  a = A;
  b = B;
  w.resize(m);
  for (int i = 0; i < m; i++) {
    x[i] = U[i];
    y[i] = V[i];
    g[x[i]].push_back({i, y[i]});
    g[y[i]].push_back({i, x[i]});
  }
  vector <int> path = {};
  dfs(0, -1, path);
  answer(S, T);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2504 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2560 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 3072 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2560 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 3072 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 3072 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -