제출 #425373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425373		arneves	통행료 (IOI18_highway)	C++17	51 / 100	269 ms	14160 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

vector<pair<int,int>> adj[150000];
int ver[150000];
int are[150000];
int visitados[150000];
int contador;

void dfs(int s){

    for(auto u: adj[s]){
        if(visitados[u.f]==0){
            visitados[u.f]++;
            are[u.s]=contador;
            ver[contador]=u.f;
            contador++;
            dfs(u.f);
        }
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {


    int M=U.size();
    if(M==N-1||1){
        vector<int> w(M,0);

        ll tamanho=ask(w);

        for(int i=0; i<M; i++){

            adj[U[i]].push_back({V[i],i});
            adj[V[i]].push_back({U[i],i});
        }

        int l=0, r=N-2, m;

        while(l<r){

            m=(l+r)/2;

            for(int i=0; i<M; i++){
                if(i<=m) w[i]=1;
                else w[i]=0;
            }

            if(ask(w)!=tamanho){
                r=m;
            }else{
                l=m+1;
            }
        }

//partimos o gráfico pela aresta l, logo os
//vertices das duas arvores que sobram serao
//os extremos da aresta l;
        int a=U[l], b=V[l];

        memset(visitados, 0, sizeof(visitados));
        memset(ver,-1, sizeof(ver));
        memset(are,-1,sizeof(are));

        visitados[b]=visitados[a]=1;
        contador=0;
        dfs(a);

        int ans1, ans2;

        l=-1;
        r=N-2;
        while(l<r){

            m=(l+r+1)/2;

            for(int i=0; i<M; i++){
                if(are[i]>=m) w[i]=1;
                else w[i]=0;
                //cout<<w[i]<<' ';
            }
            //cout<<'\n';
            if(ask(w)!=tamanho){
                l=m;
            }else{
                r=m-1;
            }
        }
        ans1=l;
        if(ans1==-1) ans1=a;
        else ans1= ver[ans1];

        memset(visitados, 0, sizeof(visitados));
        memset(ver,-1, sizeof(ver));
        memset(are,-1,sizeof(are));

        visitados[b]=visitados[a]=1;
        contador=0;
        dfs(b);

        l=-1;
        r=N-2;
        while(l<r){

            m=(l+r+1)/2;

            for(int i=0; i<M; i++){
                if(are[i]>=m) w[i]=1;
                else w[i]=0;
                //cout<<w[i]<<' ';
            }
            //cout<<'\n';
            if(ask(w)!=tamanho){
                l=m;
            }else{
                r=m-1;
            }
        }
        ans2=l;
        if(ans2==-1) ans2=b;
        else ans2= ver[ans2];

        //for(int i=0; i<M; i++) cout<<are[i]<<' '; cout<<'\n';
        //for(int i=0; i<M; i++) cout<<ver[i]<<' '; cout<<'\n';
        //for(auto u: are) cout<<u<<' '; cout<<'\n';
        answer(ans1, ans2);
        //cout<<"->"<<ans1<<' '<<ans2<<'\n';
    }else{

    }
}
/*
5 4 16 20 1 4
0 1
1 2
2 3
3 4
****************
5 4 16 20 1 3
0 1
1 2
2 3
3 4
****************
5 4 16 20 0 2
0 1
1 2
2 3
3 4
****************
5 4 16 20 3 4
0 1
1 2
2 3
3 4
*/
/*
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {

    int M=U.size();

    ll tamanho;

    vector<int> w(M,0);

    ll ultima=ask(w), atual;

    tamanho=(ultima/A);
    w[0]=1;

    int l=0, r=N-2, m;

    while(l<r){
        m=(l+r)/2;

        for(int i=0; i<M; i++){
            if(i<=m){
                w[i]=0;
            }else{
                w[i]=1;
            }
            //cout<<w[i]<<' ';
        }
        //cout<<"->"<<m<<'\n';
        atual=ask(w);

        if(atual==ultima){
            r=m-1;
        }else if(atual/B==ultima/A){
            l=m+1;
        }else{
            r=m;
        }
    }

    //cout<<l<<' '<<l+tamanho<<'\n';
    answer(l, l+tamanho);
}
*/

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