oj.uz

Submission #1099196

# Submission time Handle Problem Language Result Execution time Memory
1099196 2024-10-10T17:19:48 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 1500 ms 18352 KB 
#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N=90005;
int q;
int remedges;
int n,m;
vector<int>w;
vector<pair<int,int> >g[MAX_N],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;
bool used[MAX_N];
bool usededge[130010];
void initbfs()
{
    queue<int>q;
    q.push(root);
    used[root]=1;

    while(q.size())
    {
        int u=q.front();
        q.pop();

        for(auto [v,edge]:G[u])
        {
            if(used[v])continue;

            used[v]=1;
            usededge[edge]=1;
            g[u].push_back({v,edge});
            g[v].push_back({u,edge});
            parent[v]=u;
            paredge[v]=edge;
            depth[v]=depth[u]+1;
            q.push(v);
        }
    }
}
int onpath()
{
    int l=0,r=n-1;
    int ans;

    while(l<=r)
    {
        int mid=(l+r)/2;
        for(int u=0;u<=mid;u++)
        {
            for(auto [v,edge]:G[u])
            {
                w[edge]=1;
            }
        }
        long long ncost=ask(w);q++;
        for(int u=0;u<=mid;u++)
        {
            for(auto [v,edge]:G[u])
            {
                w[edge]=0;
            }
        }
        if(ncost!=cost)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    return ans;
}
void nodesdfs(int u)
{

    if(remedges==edges)
    {
        if(depth[u]<=remedges)nodes.push_back({depth[u],u});
    }
    else if(depth[u]==remedges)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);q++;
    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 branch,bool with)
{
    nodes.clear();
    for(int i=0;i<g[root].size();i++)
    {
        if(with)
        {
            if(i!=branch)continue;
        }
        else
        {
            if(i==branch)continue;
        }

        nodesdfs(g[root][i].first);
    }
    sort(nodes.rbegin(),nodes.rend());
    ENDS.push_back(rec(0,nodes.size()-1));
}
int solvetwo()
{
    int l=0,r=g[root].size()-1;
    int ans=-1;

    while(l<=r)
    {
        int mid=(l+r)/2;

        for(int i=0;i<=mid;i++)
        {
            w[g[root][i].second]=1;
        }
        long long ncost=ask(w);q++;
        for(int i=0;i<=mid;i++)
        {
            w[g[root][i].second]=0;
        }

        if(ncost!=cost)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    return ans;
}
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);q++;
    edges=cost/a;
    remedges=edges;

    root=onpath();
    initbfs();
    for(int i=0;i<m;i++)
    {
        if(usededge[i])continue;
        w[i]=1;
    }

    int branch=solvetwo();
    solve(branch,1);
    if(depth[ENDS[0]]==edges)
    {
        ENDS.push_back(root);
    }
    else
    {
        remedges-=depth[ENDS[0]];
        solve(branch,0);
    }

    if(q>56)while(1);

    answer(ENDS[0],ENDS[1]);
}

Compilation message

highway.cpp: In function 'void initbfs()':
highway.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for(auto [v,edge]:G[u])
      |                  ^
highway.cpp: In function 'int onpath()':
highway.cpp:59:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |             for(auto [v,edge]:G[u])
      |                      ^
highway.cpp:67:22: 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 nodesdfs(int)':
highway.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void solve(int, bool)':
highway.cpp:123: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]
  123 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp: In function 'int onpath()':
highway.cpp:80:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     return ans;
      |            ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 11 ms 5720 KB Output is correct
3 Correct 87 ms 14884 KB Output is correct
4 Correct 102 ms 15556 KB Output is correct
5 Correct 100 ms 14876 KB Output is correct
6 Correct 95 ms 15548 KB Output is correct
7 Correct 93 ms 14632 KB Output is correct
8 Correct 110 ms 15040 KB Output is correct
9 Correct 78 ms 14492 KB Output is correct
10 Correct 92 ms 15072 KB Output is correct
11 Correct 84 ms 14780 KB Output is correct
12 Correct 91 ms 15768 KB Output is correct
13 Correct 99 ms 15108 KB Output is correct
14 Correct 88 ms 14872 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6028 KB Output is correct
2 Correct 18 ms 7512 KB Output is correct
3 Correct 25 ms 7716 KB Output is correct
4 Correct 82 ms 17188 KB Output is correct
5 Correct 73 ms 16712 KB Output is correct
6 Correct 77 ms 18224 KB Output is correct
7 Correct 76 ms 13340 KB Output is correct
8 Correct 75 ms 17640 KB Output is correct
9 Correct 75 ms 14756 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 11 ms 5720 KB Output is correct
3 Correct 66 ms 12176 KB Output is correct
4 Correct 98 ms 14232 KB Output is correct
5 Correct 96 ms 14396 KB Output is correct
6 Correct 92 ms 14144 KB Output is correct
7 Correct 89 ms 14300 KB Output is correct
8 Correct 109 ms 14304 KB Output is correct
9 Correct 105 ms 15332 KB Output is correct
10 Correct 94 ms 15036 KB Output is correct
11 Correct 90 ms 14180 KB Output is correct
12 Correct 93 ms 15428 KB Output is correct
13 Correct 95 ms 14688 KB Output is correct
14 Correct 98 ms 15356 KB Output is correct
15 Correct 84 ms 14328 KB Output is correct
16 Correct 84 ms 14336 KB Output is correct
17 Correct 90 ms 14724 KB Output is correct
18 Correct 89 ms 15464 KB Output is correct
19 Correct 85 ms 14176 KB Output is correct
20 Correct 84 ms 15348 KB Output is correct
21 Correct 92 ms 16396 KB Output is correct
22 Correct 102 ms 16572 KB Output is correct
23 Correct 98 ms 15612 KB Output is correct
24 Correct 97 ms 15572 KB Output is correct
25 Correct 102 ms 18352 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5720 KB Output is correct
2 Correct 16 ms 5720 KB Output is correct
3 Correct 123 ms 15840 KB Output is correct
4 Correct 128 ms 15660 KB Output is correct
5 Correct 168 ms 16940 KB Output is correct
6 Correct 158 ms 16436 KB Output is correct
7 Correct 151 ms 16944 KB Output is correct
8 Correct 141 ms 16088 KB Output is correct
9 Correct 111 ms 11840 KB Output is correct
10 Correct 109 ms 12024 KB Output is correct
11 Correct 124 ms 13760 KB Output is correct
12 Correct 154 ms 14884 KB Output is correct
13 Correct 134 ms 15632 KB Output is correct
14 Correct 151 ms 16024 KB Output is correct
15 Correct 149 ms 15932 KB Output is correct
16 Correct 117 ms 13080 KB Output is correct
17 Correct 107 ms 16324 KB Output is correct
18 Correct 95 ms 16504 KB Output is correct
19 Correct 95 ms 16356 KB Output is correct
20 Execution timed out 3028 ms 16504 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5720 KB Output is correct
2 Correct 13 ms 5976 KB Output is correct
3 Correct 110 ms 14984 KB Output is correct
4 Correct 120 ms 14924 KB Output is correct
5 Correct 131 ms 15548 KB Output is correct
6 Correct 149 ms 16252 KB Output is correct
7 Correct 127 ms 15840 KB Output is correct
8 Correct 104 ms 15128 KB Output is correct
9 Correct 111 ms 15316 KB Output is correct
10 Correct 140 ms 16192 KB Output is correct
11 Correct 141 ms 16224 KB Output is correct
12 Correct 132 ms 16168 KB Output is correct
13 Correct 119 ms 13016 KB Output is correct
14 Correct 109 ms 12620 KB Output is correct
15 Correct 107 ms 12988 KB Output is correct
16 Correct 129 ms 12012 KB Output is correct
17 Correct 127 ms 13748 KB Output is correct
18 Correct 104 ms 12368 KB Output is correct
19 Correct 141 ms 15136 KB Output is correct
20 Correct 134 ms 15380 KB Output is correct
21 Correct 160 ms 16212 KB Output is correct
22 Correct 143 ms 15956 KB Output is correct
23 Correct 142 ms 15940 KB Output is correct
24 Correct 138 ms 15908 KB Output is correct
25 Correct 172 ms 15972 KB Output is correct
26 Correct 147 ms 15892 KB Output is correct
27 Correct 118 ms 16416 KB Output is correct
28 Correct 99 ms 16360 KB Output is correct
29 Correct 110 ms 16512 KB Output is correct
30 Correct 107 ms 16480 KB Output is correct
31 Correct 95 ms 16408 KB Output is correct
32 Execution timed out 3012 ms 16324 KB Time limit exceeded
33 Halted 0 ms 0 KB -