Submission #348893

#	Time	Username	Problem	Language	Result	Execution time	Memory
348893		juggernaut	통행료 (IOI18_highway)	C++14	51 / 100	312 ms	10408 KiB

highway

#include"highway.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
vector<pair<int,int>>g[90005];
bool vis[90005];
int id[130005];
int under[130005];
int n,m;
long long pivot;
int depth(int root){
    for(int i=0;i<n;i++)vis[i]=0;
    queue<int>q;
    int timer=0;
    q.push(root);
    vis[root]=1;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(auto to:g[v])if(!vis[to.first]){
            q.push(to.first);
            vis[to.first]=1;
            id[++timer]=to.second;
            under[timer]=to.first;
        }
    }
    int l=1,r=timer;
    while(l<r){
        int mid=(l+r+1)>>1;
        vector<int>v(m,0);
        for(int i=mid;i<=timer;i++)v[id[i]]=1;
        if(ask(v)!=pivot)l=mid;
        else r=mid-1;
    }
    return under[l];
}
void find_pair(int n,vector<int>x,vector<int>y,int a,int b){
    ::n=n;::m=x.size();
    pivot=ask(vector<int>(m,0));
    for(int i=0;i<m;i++){
        g[x[i]].push_back({y[i],i});
        g[y[i]].push_back({x[i],i});
    }
    int s=depth(depth(0));
    int t=depth(s);
    answer(s,t);
}
/*
5 4 1 2 0 4
0 1
0 2
1 3
1 4
*/

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