제출 #421961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421961		Sundavar	통행료 (IOI18_highway)	C++14	0 / 100	32 ms	1344 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
struct node{
  vector<pii> to;
  int depth = 0, start = -1, with = -1;
};
vector<node> graph;
vector<int> s;
int getEdge(int l, int r, int M, ll dist, ll length, ll A, ll B){
  if(l+1 == r) return l;
  int m = (l+r)/2;
  s.assign(M, 1);
  for(int i = l; i < r; i++) s[i] = 0;
  for(int i = l; i < m; i++) s[i] = 1;
  ll x = ask(s);
  //cout<<l<<" "<<r<<" "<<x<<" "<<dist<<endl;
  if(x == dist)
    return getEdge(m, r, M, dist, length, A, B);
  else{
    int in = (x-dist)/(B-A);
    dist += (length-in)*(B-A);
    length = in;
    return getEdge(l, m, M, dist, length, A, B);
  }
}
void BFS(int x, int y){
  queue<int> q;
  q.push(x), q.push(y);
  graph[x].start = x, graph[y].start = y;
  while(q.size() > 0){
    int curr = q.front();
    q.pop();
    for(pii& a : graph[curr].to)
      if(graph[a.first].start == -1){
        q.push(a.first);
        graph[a.first].start = graph[curr].start;
        graph[a.first].depth = graph[curr].depth + 1;
        graph[a.first].with = a.second;
      }
  }
}
int bet;
int find(int u, int N, int M, ll lenght, ll A, ll B){
  vector<int> S(M, 1);
  S[bet] = 0;
  for(int i = 0; i < N; i++)
    if(graph[i].start == u && graph[i].with != -1) S[graph[i].with] = 1;
  for(int i = 0; i < N; i++)
    if(graph[i].start != u && graph[i].with != -1) S[graph[i].with] = 0;
  int dist = (ask(S)-lenght*A)/(B-A);
  vector<int> poss;
  for(int i = 0; i < N; i++)
    if(graph[i].start == u && graph[i].depth == dist) 
      poss.push_back(i);
  while(poss.size() > 1){
    S.assign(M, 1);
    S[bet] = 0;
    for(int i = 0; i < N; i++)
      if(graph[i].start == u && graph[i].with != -1) S[graph[i].with] = 0;
    for(int i = 0; i < N; i++)
      if(graph[i].start != u && graph[i].with != -1) S[graph[i].with] = 0;
    for(int i = 0; i < poss.size()/2; i++) S[graph[poss[i]].with] = 1;
    if(ask(S) == lenght*A){
      vector<int> uj;
      for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      poss = uj;
    }
    else poss.resize(poss.size()/2);
  }
  return poss[0];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  graph.resize(N);
  int M = U.size();
  for(int i = 0; i < M; i++){
    graph[U[i]].to.push_back({V[i],i});
    graph[V[i]].to.push_back({U[i],i});
  }
  vector<int> S(M, 0);
  ll dist = ask(S), length = dist/A;
  s.resize(M, 0);
  int ind = getEdge(0, M, M, dist, length, A, B);
  cout<<ind<<endl;
  BFS(U[ind], V[ind]);
  bet = ind;
  answer(find(U[ind], N, M, length, A, B), find(V[ind], N, M, length, A, B));
}

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

highway.cpp: In function 'int find(int, int, int, ll, ll, ll)':
highway.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < poss.size()/2; i++) S[graph[poss[i]].with] = 1;
      |                    ~~^~~~~~~~~~~~~~~
highway.cpp:68:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |       for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      |                                  ~~^~~~~~~~~~~~~

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