Submission #1199145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199145		ach00	통행료 (IOI18_highway)	C++20	12 / 100	69 ms	9584 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<pair<int,int>>> adj;
int m;
int n;
void find_pair(int N, vector<int> u, vector<int> v, int a, int b) {
    n = N;
    m = u.size();
    adj.resize(n);
    for(int i = 0; i < m; i++) {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }
    vector<int> edist(m, 0);
    vector<int> dist(n,0);
    vector<bool> vis(n, false);
    vis[0] = true;
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int v = q.front(); q.pop();
        int d = dist[v];
        for(auto &e : adj[v]) {
            int id = e.second;
            int u = e.first;
            if(vis[u]) continue;
            vis[u] = true;
            dist[u] = d + 1;
            edist[id] = d + 1;
            q.push(u);
        }
    }
    vector<int> empty(m, 0);
    ll cw = ask(empty);
    ll len = cw/a;
    vector<pair<int,int>> S;
    for(int i = 0; i < m; i++) {
        S.push_back({edist[i], i});
    }
    sort(S.rbegin(), S.rend());
    int lo = 0;
    int hi = m;
    while(hi - lo > 2) {
        int p = (hi+lo)/2;
        vector<int> Q(m, 0);
        for(int j = 0; j <= p; j++) {
            Q[S[j].second] = 1;
        }
        ll as = ask(Q);
        if(as == cw) {
            lo = p + 1;
        } else {
            hi = p;
        }
    }
    int s = 0;
    int fe = -1;
    for(int y = lo; y <= hi; y++) {
        vector<int> Q(m, 0);
        for(int j = 0; j <= y; j++) {
            Q[S[j].second] = 1;
        } 
        ll as = ask(Q);
        if(as > cw) {
            fe = S[y].second;
            break;
        }
    }
    int t;
    if(dist[u[fe]] == len) t = u[fe];
    else t = v[fe];
    answer(s,t);
}

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