제출 #531274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531274		AdamGS	Highway Tolls (IOI18_highway)	C++17	100 / 100	249 ms	11376 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int MAXN=9e4+7, MAXM=13e4+7, INF=1e9+7;
vector<int>V[MAXN], kol[2], pytanie, P;
pair<int,int>kraw[MAXM];
ll dist;
int odl[MAXN], syn[MAXM], n, m;
bool ok() {
  ll x=ask(pytanie);
  return x==dist;
}
void find_pair(int N, vector<int>X, vector<int>Y, int A, int B) {
  n=N; m=X.size();
  rep(i, m) {
    pytanie.pb(0);
    kraw[i]={X[i], Y[i]};
  }
  dist=ask(pytanie);
  int p=0, k=m-1;
  while(p<k) {
    int sr=(p+k)/2;
    rep(i, m) pytanie[i]=0;
    rep(i, sr+1) pytanie[i]=1;
    if(ok()) p=sr+1; else k=sr;
  }
  rep(i, m) pytanie[i]=1;
  pytanie[p]=0;
  P.pb(p);
  for(int i=p; i<m; ++i) {
    V[kraw[i].st].pb(i);
    V[kraw[i].nd].pb(i);
  }
  queue<pair<int,int>>q;
  rep(i, n) odl[i]=INF;
  odl[kraw[p].st]=odl[kraw[p].nd]=1;
  q.push({kraw[p].st, 0});
  q.push({kraw[p].nd, 1});
  rep(i, m) syn[i]=-1;
  while(!q.empty()) {
    int v=q.front().st, r=q.front().nd; q.pop();
    for(auto i : V[v]) {
      int z=v^kraw[i].st^kraw[i].nd;
      if(odl[z]>odl[v]+1) {
        odl[z]=odl[v]+1;
        q.push({z, r});
        kol[r].pb(i);
        syn[i]=z;
        P.pb(i);
      }
    }
  }
  rep(i, 2) reverse(all(kol[i]));
  int p1=0, k1=kol[0].size();
  while(p1<k1) {
    int sr=(p1+k1)/2;
    rep(i, m) pytanie[i]=1;
    for(auto i : P) pytanie[i]=0;
    rep(i, sr+1) pytanie[kol[0][i]]=1;
    if(ok()) p1=sr+1; else k1=sr;
  }
  if(p1==kol[0].size()) p1=kraw[p].st;
  else p1=syn[kol[0][p1]];
  int p2=0, k2=kol[1].size();
  while(p2<k2) {
    int sr=(p2+k2)/2;
    rep(i, m) pytanie[i]=1;
    for(auto i : P) pytanie[i]=0;
    rep(i, sr+1) pytanie[kol[1][i]]=1;
    if(ok()) p2=sr+1; else k2=sr;
  }
  if(p2==kol[1].size()) p2=kraw[p].nd;
  else p2=syn[kol[1][p2]];
  answer(p1, p2);
}

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:68:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(p1==kol[0].size()) p1=kraw[p].st;
      |      ~~^~~~~~~~~~~~~~~
highway.cpp:78:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if(p2==kol[1].size()) p2=kraw[p].nd;
      |      ~~^~~~~~~~~~~~~~~

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