Submission #1098728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098728		MMihalev	Highway Tolls (IOI18_highway)	C++14	51 / 100	248 ms	262144 KiB

highway

#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N=90005;
int n,m;
vector<int>w;
vector<pair<int,int> >g[MAX_N];
long long edges,cost;
int root;
int a,b;
int parent[MAX_N];
int paredge[MAX_N];
int depth[MAX_N];
vector<int>ENDS;
vector<pair<int,int>>nodes;
void initdfs(int u,int par)
{
    parent[u]=par;
    for(auto [v,edge] : g[u])
    {
        if(v==par)continue;
        depth[v]=depth[u]+1;
        paredge[v]=edge;
        initdfs(v,u);
    }
}
int onpath(int l,int r)
{
    if(l==r)return l;
    int mid=(l+r)/2;

    for(int u=l;u<=mid;u++)
    {
        for(auto [v,edge]:g[u])
        {
            w[edge]=1;
        }
    }
    long long ncost=ask(w);
    for(int u=l;u<=mid;u++)
    {
        for(auto [v,edge]:g[u])
        {
            w[edge]=0;
        }
    }

    if(ncost>cost)
    {
        return onpath(l,mid);
    }
    return onpath(mid+1,r);
}
void markdfs(int u,bool f)
{
    w[paredge[u]]=f;
    for(auto [v,edge]:g[u])
    {
        if(v==parent[u])continue;
        markdfs(v,f);
    }
}
void nodesdfs(int u)
{
    nodes.push_back({depth[u],u});
    for(auto [v,edge]:g[u])
    {
        if(v==parent[u])continue;

        nodesdfs(v);
    }
}
int rec(int l,int r)
{
    if(l==r)
    {
        return nodes[l].second;
    }

    int mid=(l+r)/2;

    for(int i=l;i<=mid;i++)
    {
        w[paredge[nodes[i].second]]=1;
    }
    long long ncost=ask(w);
    for(int i=l;i<=mid;i++)
    {
        w[paredge[nodes[i].second]]=0;
    }

    if(ncost!=cost)return rec(l,mid);
    return rec(mid+1,r);
}
void solve(int l,int r)
{
    nodes.clear();
    for(int i=l;i<=r;i++)
    {
        nodesdfs(g[root][i].first);
    }
    sort(nodes.rbegin(),nodes.rend());
    ENDS.push_back(rec(0,nodes.size()-1));
}
void solvetwo(int l,int r)
{
    int mid=(l+r)/2;

    for(int i=l;i<=mid;i++)
    {
        markdfs(g[root][i].first,1);
    }
    long long ncost=ask(w);
    for(int i=l;i<=mid;i++)
    {
        markdfs(g[root][i].first,0);
    }

    if(ncost==cost)solvetwo(mid+1,r);
    else if(ncost==b*edges)solvetwo(l,mid);
    else
    {
        solve(l,mid);
        solve(mid+1,r);
    }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n=N;
    m=U.size();
    w.resize(m);
    a=A;
    b=B;

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

    cost=ask(w);
    edges=cost/a;

    root=onpath(0,n-1);
    initdfs(root,-1);

    bool twodifferent=0;

    for(int i=0;i<g[root].size();i++)
    {
        w[g[root][i].second]=1;
    }
    long long ncost=ask(w);
    if((ncost-cost)==2*(b-a))twodifferent=1;
    for(int i=0;i<g[root].size();i++)
    {
        w[g[root][i].second]=0;
    }

    if(!twodifferent)
    {
        ENDS.push_back(root);
        solve(0,g[root].size()-1);
    }
    else
    {
        solvetwo(0,g[root].size()-1);
    }

    answer(ENDS[0],ENDS[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void initdfs(int, int)':
highway.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [v,edge] : g[u])
      |              ^
highway.cpp: In function 'int onpath(int, int)':
highway.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [v,edge]:g[u])
      |                  ^
highway.cpp:44:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto [v,edge]:g[u])
      |                  ^
highway.cpp: In function 'void markdfs(int, bool)':
highway.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void nodesdfs(int)':
highway.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:151:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:157:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i=0;i<g[root].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