oj.uz

Submission #1098725

# Submission time Handle Problem Language Result Execution time Memory
1098725 2024-10-09T19:19:13 Z MMihalev Highway Tolls (IOI18_highway) C++14
11 / 100
 1500 ms 262144 KB 
#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<int>leaves;
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(g[u].size()==1)leaves.push_back(u);
}
int uu;
long long nc;
int ii;
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(ii=l;ii<=mid;ii++)
    {
        uu=leaves[ii];
        while(uu!=root)
        {
            if(w[paredge[uu]]==1)break;
            w[paredge[uu]]=1;
            uu=parent[uu];
        }
    }
    nc=ask(w);
    for(ii=l;ii<=mid;ii++)
    {
        uu=leaves[ii];
        while(uu!=root)
        {
            if(w[paredge[uu]]==0)break;
            w[paredge[uu]]=0;
            uu=parent[uu];
        }
    }

    if(cnt*b+(edges-cnt)*a==nc)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,0);
    }

    if(ncost==cost)solvetwo(mid+1,r);
    else if(ncost==b*edges)solvetwo(l,mid);
    else
    {
        int edges1=(ncost-cost)/(b-a);
        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)==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,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:173: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]
  173 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:179: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]
  179 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3416 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 1 ms 3416 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 1 ms 3416 KB Output is correct
8 Correct 1 ms 3416 KB Output is correct
9 Correct 1 ms 3416 KB Output is correct
10 Correct 1 ms 3416 KB Output is correct
11 Correct 1 ms 3252 KB Output is correct
12 Correct 1 ms 3416 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 9 ms 4032 KB Output is correct
3 Correct 76 ms 9068 KB Output is correct
4 Correct 78 ms 9036 KB Output is correct
5 Correct 80 ms 9036 KB Output is correct
6 Correct 72 ms 9028 KB Output is correct
7 Correct 78 ms 9036 KB Output is correct
8 Correct 81 ms 9044 KB Output is correct
9 Correct 77 ms 9020 KB Output is correct
10 Correct 80 ms 9044 KB Output is correct
11 Correct 74 ms 9424 KB Output is correct
12 Correct 83 ms 9980 KB Output is correct
13 Correct 77 ms 9668 KB Output is correct
14 Execution timed out 3021 ms 8964 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4440 KB Output is correct
2 Correct 17 ms 5460 KB Output is correct
3 Correct 22 ms 6476 KB Output is correct
4 Correct 72 ms 11584 KB Output is correct
5 Correct 58 ms 11532 KB Output is correct
6 Correct 65 ms 12612 KB Output is correct
7 Correct 63 ms 13316 KB Output is correct
8 Correct 61 ms 12056 KB Output is correct
9 Correct 62 ms 12348 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 11 ms 3928 KB Output is correct
3 Correct 55 ms 7876 KB Output is correct
4 Correct 84 ms 9004 KB Output is correct
5 Correct 78 ms 9084 KB Output is correct
6 Correct 91 ms 9116 KB Output is correct
7 Correct 70 ms 9044 KB Output is correct
8 Correct 83 ms 9084 KB Output is correct
9 Correct 86 ms 9044 KB Output is correct
10 Correct 80 ms 9048 KB Output is correct
11 Execution timed out 3057 ms 9140 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -