제출 #596893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596893		Sam_a17	통행료 (IOI18_highway)	C++14	100 / 100	270 ms	19544 KiB

highway

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

long long ask(const std::vector<int> &w);
void answer(int s, int t);

const int maxN = 2e5 + 10;
vector<pair<int, int>> adj[maxN], g[maxN];
int n, m, u[maxN], v[maxN];
long long a, b;

template<typename F>
void pr(F a) {
  cerr << a << endl;
}

template<typename T>
void pr(vector<T>& a) {
  cerr << "[ ";
  for(auto i: a) {
    cerr << i << " ";
  }
  cerr << "]" << endl;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N, m = sz(U), a = A, b = B;
  vector<int> to_ask(m, 0);
  long long start = ask(to_ask);
  bool flag = true;

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

    u[i] = U[i], v[i] = V[i];
	}

  int ina = 0, inb = m - 1, res = -1;
  while(ina <= inb) {
    int mid = (ina + inb) / 2;
    vector<int> toask(m, 0);
    for(int i = 0; i <= mid; i++) {
      toask[i] = 1;
    }
    long long ansi = ask(toask);

    if(ansi != start) {
      res = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }

  // we get edge
  // u[res]: v[res]

  vector<int> left, right;
  vector<bool> vis(n);
  queue<pair<int, int>> q;
  
  q.push({u[res], 1});
  q.push({v[res], 2});

  left.push_back(u[res]);
  right.push_back(v[res]);

  vis[u[res]] = vis[v[res]] = true;

  while(!q.empty()) {
    auto u = q.front();
    q.pop();

    for(auto i: adj[u.first]) {
      if(vis[i.first]) continue;
      vis[i.first] = true;
      if(u.second == 1) {
        left.push_back(i.first);
      } else {
        right.push_back(i.first);
      }
      q.push({i.first, u.second});
    }
  }

  // pr(left);
  // pr(right);

  auto solve = [&](vector<int>& nodes)->int {
    int ina = 0, inb = sz(nodes) - 1, res = -1;
    while(ina <= inb) {
      int mid = (ina + inb) / 2;
      vector<int> toask(m, 1), del(n);
      for(int i = mid + 1; i < sz(nodes); i++) {
        del[nodes[i]] = 1;
      }

      for(int i = 0; i < m; i++) {
        if(!del[u[i]] && !del[v[i]]) {
          toask[i] = 0;
        }
      }

      long long ansi = ask(toask);

      if(ansi == start) {
        res = mid;
        inb = mid - 1;
      } else {
        ina = mid + 1;
      }
    }
    // pr(res);
    assert(res != -1);
    return nodes[res];
  };

  answer(solve(left), solve(right));
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In lambda function:
highway.cpp:101:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |       for(int i = mid + 1; i < sz(nodes); i++) {
      |                              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:8: warning: unused variable 'flag' [-Wunused-variable]
   36 |   bool flag = true;
      |        ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31