oj.uz

Submission #1098724

# Submission time Handle Problem Language Result Execution time Memory
1098724 2024-10-09T19:18:24 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 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++)
    {
        uu=leaves[i];
        while(uu!=root)
        {
            if(w[paredge[uu]]==1)break;
            w[paredge[uu]]=1;
            uu=parent[uu];
        }
    }
    nc=ask(w);
    for(int i=l;i<=mid;i++)
    {
        uu=leaves[i];
        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:172: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]
  172 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:178: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]
  178 |     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 3412 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 4020 KB Output is correct
3 Correct 79 ms 9020 KB Output is correct
4 Correct 80 ms 9032 KB Output is correct
5 Correct 74 ms 9040 KB Output is correct
6 Correct 87 ms 9020 KB Output is correct
7 Correct 73 ms 9052 KB Output is correct
8 Correct 85 ms 9028 KB Output is correct
9 Correct 81 ms 9084 KB Output is correct
10 Correct 77 ms 9036 KB Output is correct
11 Correct 80 ms 9544 KB Output is correct
12 Correct 84 ms 10144 KB Output is correct
13 Correct 79 ms 9496 KB Output is correct
14 Execution timed out 3020 ms 9124 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 5376 KB Output is correct
3 Correct 21 ms 6488 KB Output is correct
4 Correct 62 ms 11576 KB Output is correct
5 Correct 63 ms 11584 KB Output is correct
6 Correct 65 ms 12608 KB Output is correct
7 Correct 64 ms 13372 KB Output is correct
8 Correct 60 ms 12104 KB Output is correct
9 Correct 62 ms 12344 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 9 ms 3928 KB Output is correct
3 Correct 61 ms 7868 KB Output is correct
4 Correct 98 ms 9404 KB Output is correct
5 Correct 72 ms 9032 KB Output is correct
6 Correct 91 ms 9040 KB Output is correct
7 Correct 86 ms 9036 KB Output is correct
8 Correct 83 ms 9040 KB Output is correct
9 Correct 84 ms 9040 KB Output is correct
10 Correct 78 ms 9040 KB Output is correct
11 Execution timed out 3049 ms 8956 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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