oj.uz

Submission #1098728

# Submission time Handle Problem Language Result Execution time Memory
1098728 2024-10-09T19:31:51 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 248 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<pair<int,int>>nodes;
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 nodesdfs(int u)
{
    nodes.push_back({depth[u],u});
    for(auto [v,edge]:g[u])
    {
        if(v==parent[u])continue;

        nodesdfs(v);
    }
}
int rec(int l,int r)
{
    if(l==r)
    {
        return nodes[l].second;
    }

    int mid=(l+r)/2;

    for(int i=l;i<=mid;i++)
    {
        w[paredge[nodes[i].second]]=1;
    }
    long long ncost=ask(w);
    for(int i=l;i<=mid;i++)
    {
        w[paredge[nodes[i].second]]=0;
    }

    if(ncost!=cost)return rec(l,mid);
    return rec(mid+1,r);
}
void solve(int l,int r)
{
    nodes.clear();
    for(int i=l;i<=r;i++)
    {
        nodesdfs(g[root][i].first);
    }
    sort(nodes.rbegin(),nodes.rend());
    ENDS.push_back(rec(0,nodes.size()-1));
}
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
    {
        solve(l,mid);
        solve(mid+1,r);
    }
}
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);
    }
    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 nodesdfs(int)':
highway.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:151: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]
  151 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:157: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]
  157 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 10 ms 3392 KB Output is correct
3 Correct 86 ms 9676 KB Output is correct
4 Correct 92 ms 9852 KB Output is correct
5 Correct 101 ms 9668 KB Output is correct
6 Correct 81 ms 9688 KB Output is correct
7 Correct 94 ms 9876 KB Output is correct
8 Correct 86 ms 9852 KB Output is correct
9 Correct 84 ms 9756 KB Output is correct
10 Correct 98 ms 9984 KB Output is correct
11 Correct 83 ms 10464 KB Output is correct
12 Correct 99 ms 11272 KB Output is correct
13 Correct 96 ms 10828 KB Output is correct
14 Correct 83 ms 10056 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3672 KB Output is correct
2 Correct 15 ms 5108 KB Output is correct
3 Correct 23 ms 6352 KB Output is correct
4 Correct 79 ms 12824 KB Output is correct
5 Correct 72 ms 12820 KB Output is correct
6 Correct 73 ms 13760 KB Output is correct
7 Correct 71 ms 14772 KB Output is correct
8 Correct 83 ms 13240 KB Output is correct
9 Correct 77 ms 13340 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 10 ms 3160 KB Output is correct
3 Correct 62 ms 8532 KB Output is correct
4 Correct 83 ms 9840 KB Output is correct
5 Correct 86 ms 9684 KB Output is correct
6 Correct 96 ms 9752 KB Output is correct
7 Correct 84 ms 9840 KB Output is correct
8 Correct 96 ms 9832 KB Output is correct
9 Correct 92 ms 9832 KB Output is correct
10 Correct 84 ms 9796 KB Output is correct
11 Correct 91 ms 10412 KB Output is correct
12 Correct 96 ms 10340 KB Output is correct
13 Correct 94 ms 10048 KB Output is correct
14 Correct 87 ms 11204 KB Output is correct
15 Correct 95 ms 9668 KB Output is correct
16 Correct 81 ms 9852 KB Output is correct
17 Correct 102 ms 9660 KB Output is correct
18 Correct 99 ms 11068 KB Output is correct
19 Correct 92 ms 9816 KB Output is correct
20 Correct 86 ms 11328 KB Output is correct
21 Correct 81 ms 9748 KB Output is correct
22 Correct 74 ms 10180 KB Output is correct
23 Correct 79 ms 9544 KB Output is correct
24 Correct 82 ms 10064 KB Output is correct
25 Correct 104 ms 14064 KB Output is correct

Subtask #5
0 / 18.0

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