oj.uz

Submission #1099197

# Submission time Handle Problem Language Result Execution time Memory
1099197 2024-10-10T17:21:29 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 1500 ms 18376 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;
            if(remedges!=edges)return ans;
        }
        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:52:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     int 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 4680 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 2 ms 4696 KB Output is correct
2 Correct 10 ms 5720 KB Output is correct
3 Correct 88 ms 14936 KB Output is correct
4 Correct 100 ms 15336 KB Output is correct
5 Correct 95 ms 15236 KB Output is correct
6 Correct 90 ms 15500 KB Output is correct
7 Correct 92 ms 14584 KB Output is correct
8 Correct 117 ms 14856 KB Output is correct
9 Correct 98 ms 14320 KB Output is correct
10 Correct 97 ms 15032 KB Output is correct
11 Correct 90 ms 14752 KB Output is correct
12 Correct 91 ms 15692 KB Output is correct
13 Correct 100 ms 15092 KB Output is correct
14 Correct 95 ms 14992 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5976 KB Output is correct
2 Correct 20 ms 7476 KB Output is correct
3 Correct 30 ms 7656 KB Output is correct
4 Correct 73 ms 16940 KB Output is correct
5 Correct 69 ms 16612 KB Output is correct
6 Correct 75 ms 18376 KB Output is correct
7 Correct 72 ms 13424 KB Output is correct
8 Correct 73 ms 17548 KB Output is correct
9 Correct 77 ms 14596 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 10 ms 5720 KB Output is correct
3 Correct 69 ms 12156 KB Output is correct
4 Correct 105 ms 14408 KB Output is correct
5 Correct 86 ms 14168 KB Output is correct
6 Correct 93 ms 14396 KB Output is correct
7 Correct 104 ms 14144 KB Output is correct
8 Correct 92 ms 14152 KB Output is correct
9 Correct 102 ms 15512 KB Output is correct
10 Correct 95 ms 14940 KB Output is correct
11 Correct 94 ms 14340 KB Output is correct
12 Correct 92 ms 15664 KB Output is correct
13 Correct 95 ms 14816 KB Output is correct
14 Correct 87 ms 15336 KB Output is correct
15 Correct 83 ms 14140 KB Output is correct
16 Correct 97 ms 14304 KB Output is correct
17 Correct 90 ms 14720 KB Output is correct
18 Correct 91 ms 15260 KB Output is correct
19 Correct 90 ms 14584 KB Output is correct
20 Correct 89 ms 15264 KB Output is correct
21 Correct 103 ms 16488 KB Output is correct
22 Correct 105 ms 16360 KB Output is correct
23 Correct 93 ms 15608 KB Output is correct
24 Correct 96 ms 15696 KB Output is correct
25 Correct 104 ms 18312 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5720 KB Output is correct
2 Correct 10 ms 5832 KB Output is correct
3 Correct 112 ms 15856 KB Output is correct
4 Correct 119 ms 15632 KB Output is correct
5 Correct 149 ms 16976 KB Output is correct
6 Correct 153 ms 16332 KB Output is correct
7 Correct 151 ms 17156 KB Output is correct
8 Correct 146 ms 16068 KB Output is correct
9 Correct 114 ms 11828 KB Output is correct
10 Correct 102 ms 12020 KB Output is correct
11 Correct 121 ms 13500 KB Output is correct
12 Correct 154 ms 15152 KB Output is correct
13 Correct 121 ms 15620 KB Output is correct
14 Correct 150 ms 16036 KB Output is correct
15 Correct 144 ms 16112 KB Output is correct
16 Correct 118 ms 13092 KB Output is correct
17 Correct 86 ms 16180 KB Output is correct
18 Correct 100 ms 16532 KB Output is correct
19 Correct 102 ms 16344 KB Output is correct
20 Execution timed out 3066 ms 16548 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5720 KB Output is correct
2 Correct 15 ms 5976 KB Output is correct
3 Correct 110 ms 14960 KB Output is correct
4 Correct 119 ms 15256 KB Output is correct
5 Correct 131 ms 15568 KB Output is correct
6 Correct 150 ms 16464 KB Output is correct
7 Correct 122 ms 15900 KB Output is correct
8 Correct 113 ms 15132 KB Output is correct
9 Correct 117 ms 15308 KB Output is correct
10 Correct 134 ms 16208 KB Output is correct
11 Correct 136 ms 16212 KB Output is correct
12 Correct 129 ms 16152 KB Output is correct
13 Correct 117 ms 13012 KB Output is correct
14 Correct 93 ms 12024 KB Output is correct
15 Correct 105 ms 12996 KB Output is correct
16 Correct 98 ms 12012 KB Output is correct
17 Correct 119 ms 13520 KB Output is correct
18 Correct 103 ms 12440 KB Output is correct
19 Correct 159 ms 15036 KB Output is correct
20 Correct 144 ms 15396 KB Output is correct
21 Correct 149 ms 16036 KB Output is correct
22 Correct 156 ms 15952 KB Output is correct
23 Correct 143 ms 15888 KB Output is correct
24 Correct 144 ms 15928 KB Output is correct
25 Correct 162 ms 16112 KB Output is correct
26 Correct 147 ms 15888 KB Output is correct
27 Correct 115 ms 16372 KB Output is correct
28 Correct 106 ms 16236 KB Output is correct
29 Correct 120 ms 16708 KB Output is correct
30 Correct 130 ms 16308 KB Output is correct
31 Correct 97 ms 16440 KB Output is correct
32 Execution timed out 3013 ms 16244 KB Time limit exceeded
33 Halted 0 ms 0 KB -