Submission #1098384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098384	2024-10-09T10:58:07 Z	MMihalev	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 KB

highway

#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N=1e5+5;
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>leaves;
vector<int>ends;
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 leavesdfs(int u)
{
    for(auto [v,edge]:g[u])
    {
        if(v==parent[u])continue;

        leavesdfs(v);
    }
    if(u!=root g[u].size()==1)leaves.push_back(u);
}
void goup(int u,bool f)
{
    if(u==root)return;
    w[paredge[u]]=f;
    goup(parent[u]);
}
int rec(int l,int r,int cnt)
{
    if(l==r)
    {
        int u=leaves[l];
        int ups=depth[u]-cnt;
        while(ups--)
        {
            u=parent[u];
        }
        return u;
    }

    int mid=(l+r)/2;

    for(int i=l;i<=mid;i++)
    {
        goup(leaves[i],1);
    }
    long long ncost=ask(w);
    for(int i=l;i<=mid;i++)
    {
        goup(leaves[i],0);
    }

    if((ncost-cost)/b==edges)return rec(l,mid,cnt);
    return rec(mid+1,r,cnt);
}
void solve(int l,int r,int cnt)
{
    leaves.clear();
    for(int i=l;i<=r;i++)
    {
        leavesdfs(g[root][i].first);
    }

    ends.push_back(rec(0,leaves.size()-1,cnt));
}
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,1);
    }

    if((ncost-cost)/b==0)solvetwo(mid+1,r);
    else if((ncost-cost)/b==edges)solvetwo(l,mid);
    else
    {
        int edges1=(ncost-cost)/b;
        solve(l,mid,edges1);
        solve(mid+1,r,edges-edges1);
    }
}
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)/b==2)twodifferent=1;
    for(int i=0;i<g[root].size();i++)
    {
        w[g[root][i].second]=1;
    }

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

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

Compilation message

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 leavesdfs(int)':
highway.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp:73:15: error: expected ')' before 'g'
   73 |     if(u!=root g[u].size()==1)leaves.push_back(u);
      |       ~       ^~
      |               )
highway.cpp: In function 'void goup(int, bool)':
highway.cpp:79:19: error: too few arguments to function 'void goup(int, bool)'
   79 |     goup(parent[u]);
      |                   ^
highway.cpp:75:6: note: declared here
   75 | void goup(int u,bool f)
      |      ^~~~
highway.cpp: In function 'void solve(int, int, int)':
highway.cpp:117:5: error: reference to 'ends' is ambiguous
  117 |     ends.push_back(rec(0,leaves.size()-1,cnt));
      |     ^~~~
In file included from /usr/include/c++/10/iostream:39,
                 from highway.cpp:2:
/usr/include/c++/10/ostream:693:5: note: candidates are: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::ends(std::basic_ostream<_CharT, _Traits>&)'
  693 |     ends(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
highway.cpp:17:12: note:                 'std::vector<int> ends'
   17 | vector<int>ends;
      |            ^~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:164: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]
  164 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:170: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]
  170 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:177:9: error: reference to 'ends' is ambiguous
  177 |         ends.push_back(root);
      |         ^~~~
In file included from /usr/include/c++/10/iostream:39,
                 from highway.cpp:2:
/usr/include/c++/10/ostream:693:5: note: candidates are: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::ends(std::basic_ostream<_CharT, _Traits>&)'
  693 |     ends(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
highway.cpp:17:12: note:                 'std::vector<int> ends'
   17 | vector<int>ends;
      |            ^~~~
highway.cpp:185:12: error: reference to 'ends' is ambiguous
  185 |     answer(ends[0],ends[1]);
      |            ^~~~
In file included from /usr/include/c++/10/iostream:39,
                 from highway.cpp:2:
/usr/include/c++/10/ostream:693:5: note: candidates are: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::ends(std::basic_ostream<_CharT, _Traits>&)'
  693 |     ends(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
highway.cpp:17:12: note:                 'std::vector<int> ends'
   17 | vector<int>ends;
      |            ^~~~
highway.cpp:185:20: error: reference to 'ends' is ambiguous
  185 |     answer(ends[0],ends[1]);
      |                    ^~~~
In file included from /usr/include/c++/10/iostream:39,
                 from highway.cpp:2:
/usr/include/c++/10/ostream:693:5: note: candidates are: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::ends(std::basic_ostream<_CharT, _Traits>&)'
  693 |     ends(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
highway.cpp:17:12: note:                 'std::vector<int> ends'
   17 | vector<int>ends;
      |            ^~~~