oj.uz

Submission #1098719

# Submission time Handle Problem Language Result Execution time Memory
1098719 2024-10-09T19:12:23 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);
}
void goup(int u,bool f)
{
    if(u==root)return;
    //if(w[paredge[u]]==f)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(cnt*b+(edges-cnt)*a==ncost)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:165: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]
  165 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:171: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]
  171 |     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 3416 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 4016 KB Output is correct
3 Correct 80 ms 9044 KB Output is correct
4 Correct 85 ms 9036 KB Output is correct
5 Correct 84 ms 9032 KB Output is correct
6 Correct 97 ms 9044 KB Output is correct
7 Correct 86 ms 9180 KB Output is correct
8 Correct 81 ms 9044 KB Output is correct
9 Correct 83 ms 9044 KB Output is correct
10 Correct 83 ms 9052 KB Output is correct
11 Correct 89 ms 9424 KB Output is correct
12 Correct 94 ms 10372 KB Output is correct
13 Correct 104 ms 9736 KB Output is correct
14 Execution timed out 3100 ms 9120 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 14 ms 5464 KB Output is correct
3 Correct 21 ms 6484 KB Output is correct
4 Correct 63 ms 11588 KB Output is correct
5 Correct 62 ms 11584 KB Output is correct
6 Correct 61 ms 12612 KB Output is correct
7 Correct 76 ms 13376 KB Output is correct
8 Correct 64 ms 12096 KB Output is correct
9 Correct 61 ms 12288 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 10 ms 4024 KB Output is correct
3 Correct 68 ms 7892 KB Output is correct
4 Correct 88 ms 9036 KB Output is correct
5 Correct 82 ms 9040 KB Output is correct
6 Correct 92 ms 9032 KB Output is correct
7 Correct 78 ms 9012 KB Output is correct
8 Correct 81 ms 9024 KB Output is correct
9 Correct 89 ms 9444 KB Output is correct
10 Correct 81 ms 9016 KB Output is correct
11 Execution timed out 3043 ms 9156 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 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 177 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -