Submission #1195525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195525		simplemind_31	통행료 (IOI18_highway)	C++20	0 / 100	6 ms	4196 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int,int>> graph[90001];
vector<int> dist(90001,0);
vector<pair<int,int>> padre(90001,{0,0});
void dfs(int now,int 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;
  }
}
vector<int> aske;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
  int M = U.size();
  for(int i=0;i<M;i++){
    graph[U[i]].push_back({V[i],i});
    graph[V[i]].push_back({U[i],i});
  }
  dfs(0,-1);
  aske.assign(M,0);
  ll res=ask(aske);
  ll nue=0;
  for(int i=0;i<N;i++){
    if(dist[i]==res/A){
      aske[padre[i].second]=1;
      nue=ask(aske);
      if(nue!=res){
        answer(0,i);
        break;
      }
      aske[padre[i].second]=0;
    }
  }
}

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