제출 #284560

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

highway

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

const int nmax=130000+42;
/*
long long ask(vector<int> w)
{
    for(auto k:w)cout<<k<<" ";
    long long ret;
    cin>>ret;
    return ret;
}

void answer(int s,int t)
{
    cout<<"s= "<<s<<" t= "<<t<<endl;
}
*/
int M;

vector<int> cur;

bool can[nmax];

vector< pair<int/*to*/,int/*id*/> > adj[nmax];

vector<int> possible;

int up[nmax],up_edge[nmax];

void dfs_create(int node,int par)
{
    //cout<<"create "<<node<<" "<<par<<endl;

    up[node]=par;

    possible.push_back(node);

    for(auto k:adj[node])
        if(k.first!=par)
        {
            dfs_create(k.first,node);
            up_edge[k.first]=k.second;
        }
}

long long SHOULD;

bool mark[nmax];

vector<int> other;

void dfs_other(int node,int par)
{
    for(auto k:adj[node])
        if(k.first!=par)
        {
            other.push_back(k.second);
            dfs_other(k.first,node);
        }
}
int solve(int between,int node,int par)
{
    possible={};

    dfs_create(node,par);

    other={between};

    dfs_other(par,node);
    /*
    cout<<"solve "<<node<<" "<<par<<" "<<between<<endl;
    cout<<"possible: ";for(auto k:possible)cout<<k<<" ";cout<<endl;
    cout<<"other: ";for(auto k:other)cout<<k<<" ";cout<<endl;
    */
    while(possible.size()>1)
    {
        //cout<<"possible: ";for(auto k:possible)cout<<k<<" ";cout<<endl;

        memset(mark,0,sizeof(mark));

        int mid=possible.size()/2;

        vector<int> groups[2]={{},{}};

        for(int i=0;i<possible.size();i++)
        {
            if(i<mid)groups[0].push_back(possible[i]);
            else groups[1].push_back(possible[i]);
        }

        for(int i=0;i<M;i++)cur[i]=1;

        for(auto k:other)cur[k]=0;

        for(auto k:groups[0])
        {
            int in=k;

            while(in!=node&&mark[in]==0)
            {
                mark[in]=1;

                cur[up_edge[in]]=0;

                in=up[in];
            }
        }

        if(ask(cur)==SHOULD)possible=groups[0];
        else possible=groups[1];
    }

    return possible[0];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    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});
    }

    vector<int> on={};

    for(int j=0;j<M;j++)
    {
        cur.push_back(0);
        on.push_back(0);
    }

    long long dist=ask(on)/A;

    SHOULD=dist*A;

    for(int i=0;i<M;i++)
        on[i]=i;

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

        vector<int> groups[2]={{},{}};

        for(int i=0;i<on.size();i++)
            groups[i%2].push_back(on[i]);

        for(int j=0;j<M;j++)cur[j]=1;

        //test groups[0]
        for(auto k:groups[0])
            cur[k]=0;

        if(ask(cur)!=dist*B)on=groups[0];
        else on=groups[1];//everything is heavy
    }

    //cout<<"on= "<<on[0]<<endl;

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

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

    answer(s,t);
}

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

highway.cpp: In function 'int solve(int, int, int)':
highway.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i=0;i<possible.size();i++)
      |                     ~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int i=0;i<on.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