제출 #594323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594323		TimDee	Highway Tolls (IOI18_highway)	C++14	12 / 100	132 ms	8804 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
void find_pair(int n, vector<int>u, vector<int> v, int a, int b) {
    int m=u.size();
    vector<int> paiu(m,1);
    int dist=ask(paiu)/b;
    vector<vector<pair<int,int>>> adj(n);
    for (int i=0; i<m; ++i) {
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
    }
    queue<int> q;
    q.push(0);
    vector<int> d(n,0);
    vector<int> D;
    vector<int> vis(n,0); vis[0]=1;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (auto it:adj[u]) {
            int v=it.first;
            if (!vis[v]) {
                d[v]=d[u]+1;
                q.push(v);
                vis[v]=1;
            }
        }
    }
    for (int i=0; i<n; ++i) {
        if (d[i]==dist) D.push_back(i);
    }
    int l=0, r=D.size()-1;
    vector<int> scuza(m,1);
    while (l<r) {
        int mid=(l+r+1)/2;
        paiu=scuza;
        for (int i=l; i<mid; ++i) {
            for (auto it:adj[D[i]]) {
                paiu[it.second]=0;
            }
        }
        int x=ask(paiu);
        if (x<dist*b) r=mid-1;
        else l=mid;
    }
    answer(0,D[r]);
}

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