제출 #1196602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196602		simplemind_31	통행료 (IOI18_highway)	C++20	12 / 100	281 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> graph;
vector<ll> dist;
vector<pair<ll,ll>> padre;
void dfs(ll now,ll ante){
  for(auto u:graph[now]){
    if(u.first==ante){
      continue;
    }
    padre[u.first].first=now;
    padre[u.first].second=u.second;
    dist[u.first]=dist[now]+1;
    dfs(u.first,now);
  }
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B){
  graph.clear();
  graph.resize(N);
  dist.assign(N,0);
  padre.assign(N,{0,0});
  ll M=U.size();
  for(ll i=0;i<M;i++){
    graph[U[i]].push_back({V[i],i});
    graph[V[i]].push_back({U[i],i});
  }
  dfs(0,-1);
  vector<int> aske(M,0);
  vector<int> second;
  ll res=ask(aske);
  ll nue=0,con=0,con1=0;
  for(ll i=1;i<N;i++){
    if(dist[i]*A==res){
      aske[padre[i].second]=1;
      con++;
    }
  }
  res+=-A+B;
  while(con>1){
    second=aske;
    con1=con;
    for(int i=0;i<M;i++){
      if(second[i] && con1>(con/2)){
        second[i]=0;
        con1--;
      }
    }
    nue=ask(second);
    if(nue==res){
      res=nue;
      aske=second;
      con=con1;
    }else{
      for(int i=0;i<M;i++){
        if(second[i]){
          aske[i]=0;
        }
      }
      con-=con1;
    }
  }
  for(int i=0;i<M;i++){
    if(aske[i]){
      for(int j=0;j<N;j++){
        if(padre[j].second==i){
          answer(0,j);
          return;
        }
      }
    }
  }
}

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