Submission #1098389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098389	2024-10-09T10:59:39 Z	MMihalev	Highway Tolls (IOI18_highway)	C++14	6 / 100	1500 ms	262144 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],f);
}
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: 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++)
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3009 ms	3924 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3025 ms	3672 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	4696 KB	Output is correct
2	Correct	17 ms	5720 KB	Output is correct
3	Correct	22 ms	6832 KB	Output is correct
4	Correct	65 ms	11936 KB	Output is correct
5	Correct	62 ms	11840 KB	Output is correct
6	Correct	65 ms	12868 KB	Output is correct
7	Correct	60 ms	13684 KB	Output is correct
8	Correct	63 ms	12388 KB	Output is correct
9	Correct	67 ms	12648 KB	Output is correct