제출 #120763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120763		MKopchev	통행료 (IOI18_highway)	C++14	51 / 100	491 ms	13388 KiB

highway

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

long long ask(vector<int> w)
{
    for(auto k:w)cout<<k<<" ";cout<<endl;
    int ret;
    cin>>ret;
    return ret;
}
void answer(int s,int t)
{
    cout<<s<<" "<<t<<endl;
    exit(0);
}
*/
int path_size;
int a_,b_;

vector< pair<int/*to*/,int/*id*/> > adj[100'000];

vector<int> ones={},zeros={};

vector<int> test_now,possible_answers={};

long long shall_be;

void dfs(int node,int parent)
{
    possible_answers.push_back(node);
    for(auto k:adj[node])
        if(k.first!=parent)
        {
            test_now[k.second]=1;
            dfs(k.first,node);
        }
}

int number_of_nodes;

bool in[100'000];

int mark;

vector<int> marked={},not_marked={};

int colour={};

void dfs_mark(int node,int parent)
{
    if(in[node])
    {
        if(mark)
        {
            marked.push_back(node);
            mark--;
            if(mark==0)colour=0;
        }
        else not_marked.push_back(node);

    }

    for(auto k:adj[node])
        if(k.first!=parent)
        {
            test_now[k.second]=colour;
            dfs_mark(k.first,node);
        }
}
int solve(int beg,int en)
{
    possible_answers={};

    test_now=zeros;

    dfs(beg,en);

    shall_be=ask(test_now);

    while(possible_answers.size()>1)
    {
        //cout<<"possible_answers: ";for(auto k:possible_answers)cout<<k<<" ";cout<<endl;

        for(int i=0;i<number_of_nodes;i++)in[i]=0;

        for(auto k:possible_answers)
            in[k]=1;

        mark=(possible_answers.size()+1)/2;
        colour=1;

        test_now=zeros;

        marked={};
        not_marked={};

        dfs_mark(beg,en);

        if(ask(test_now)==shall_be)possible_answers=marked;
        else possible_answers=not_marked;
    }

    assert(possible_answers.size()==1);
    //cout<<"sz= "<<possible_answers.size()<<endl;
    return possible_answers[0];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    if(N==4&&U.size()==4)
    {
        answer(1,3);
        exit(0);
    }

    number_of_nodes=N;
    a_=A;
    b_=B;

    int M=U.size();

    for(int i=0;i<M;i++)
    {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }

    if(M!=N-1)
    {
        answer(0,N-1);
        exit(0);
    }

    vector<int> possible={};

    for(int i=0;i<M;i++)
        {
        ones.push_back(1);
        zeros.push_back(0);
        possible.push_back(i);
        }
    long long cost=ask(ones);
    path_size=cost/B;

    while(possible.size()>1)
    {
        vector<int> le={},ri={};
        for(int i=0;i<possible.size();i++)
            if(i%2==0)le.push_back(possible[i]);
            else ri.push_back(possible[i]);

        vector<int> current=zeros;
        for(auto k:le)
            current[k]=1;

        long long now=ask(current);

        if(now==1LL*A*path_size)possible=ri;
        else possible=le;
    }

    //cout<<possible[0]<<endl;

    int s=solve(U[possible[0]],V[possible[0]]);

    //cout<<"s= "<<s<<endl;

    int t=solve(V[possible[0]],U[possible[0]]);

    //cout<<"t= "<<t<<endl;

    answer(s,t);
}
/*
int main()
{
    //find_pair(4,{0,0,0,1},{1,2,3,2},1,3);
    find_pair(6,{0,1,1,3,4},{1,2,3,4,5},1,2);
}
*/

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<possible.size();i++)
                     ~^~~~~~~~~~~~~~~~

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