oj.uz

Submission #1099194

# Submission time Handle Problem Language Result Execution time Memory
1099194 2024-10-10T17:16:35 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 1500 ms 19004 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(depth[u]>remedges)return;
    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:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void solve(int, bool)':
highway.cpp:118: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]
  118 |     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 4440 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 4 ms 4696 KB Output is correct
8 Correct 2 ms 4440 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 4440 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 96 ms 14872 KB Output is correct
4 Correct 104 ms 15388 KB Output is correct
5 Correct 112 ms 14976 KB Output is correct
6 Correct 113 ms 15388 KB Output is correct
7 Correct 90 ms 14496 KB Output is correct
8 Correct 94 ms 14940 KB Output is correct
9 Correct 97 ms 14408 KB Output is correct
10 Correct 112 ms 14956 KB Output is correct
11 Correct 86 ms 13560 KB Output is correct
12 Correct 89 ms 14460 KB Output is correct
13 Correct 88 ms 14236 KB Output is correct
14 Correct 84 ms 14644 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5464 KB Output is correct
2 Correct 16 ms 6716 KB Output is correct
3 Correct 29 ms 7404 KB Output is correct
4 Correct 69 ms 14608 KB Output is correct
5 Correct 66 ms 13220 KB Output is correct
6 Correct 71 ms 17396 KB Output is correct
7 Correct 71 ms 13096 KB Output is correct
8 Correct 65 ms 15500 KB Output is correct
9 Correct 73 ms 13436 KB Output is correct

Subtask #4
33.0 / 33.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 74 ms 12168 KB Output is correct
4 Correct 97 ms 14400 KB Output is correct
5 Correct 85 ms 14156 KB Output is correct
6 Correct 99 ms 14372 KB Output is correct
7 Correct 84 ms 14188 KB Output is correct
8 Correct 86 ms 14364 KB Output is correct
9 Correct 107 ms 15540 KB Output is correct
10 Correct 97 ms 15068 KB Output is correct
11 Correct 105 ms 14444 KB Output is correct
12 Correct 104 ms 15208 KB Output is correct
13 Correct 107 ms 14408 KB Output is correct
14 Correct 95 ms 14264 KB Output is correct
15 Correct 84 ms 14380 KB Output is correct
16 Correct 90 ms 14404 KB Output is correct
17 Correct 104 ms 14672 KB Output is correct
18 Correct 92 ms 14404 KB Output is correct
19 Correct 91 ms 14392 KB Output is correct
20 Correct 85 ms 13292 KB Output is correct
21 Correct 98 ms 16368 KB Output is correct
22 Correct 102 ms 16384 KB Output is correct
23 Correct 93 ms 15548 KB Output is correct
24 Correct 90 ms 15756 KB Output is correct
25 Correct 108 ms 19004 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 15 ms 5720 KB Output is correct
3 Correct 121 ms 15868 KB Output is correct
4 Correct 121 ms 15512 KB Output is correct
5 Correct 147 ms 16952 KB Output is correct
6 Correct 151 ms 16408 KB Output is correct
7 Correct 141 ms 17352 KB Output is correct
8 Correct 143 ms 16064 KB Output is correct
9 Correct 111 ms 11832 KB Output is correct
10 Correct 109 ms 12020 KB Output is correct
11 Correct 118 ms 13956 KB Output is correct
12 Correct 153 ms 14948 KB Output is correct
13 Correct 134 ms 15628 KB Output is correct
14 Correct 145 ms 16032 KB Output is correct
15 Correct 162 ms 15992 KB Output is correct
16 Correct 123 ms 13112 KB Output is correct
17 Correct 89 ms 16164 KB Output is correct
18 Correct 99 ms 16336 KB Output is correct
19 Correct 97 ms 16332 KB Output is correct
20 Execution timed out 3092 ms 16664 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5720 KB Output is correct
2 Correct 12 ms 5828 KB Output is correct
3 Correct 101 ms 14984 KB Output is correct
4 Correct 125 ms 15124 KB Output is correct
5 Correct 119 ms 15728 KB Output is correct
6 Correct 136 ms 16392 KB Output is correct
7 Correct 114 ms 15748 KB Output is correct
8 Correct 116 ms 15116 KB Output is correct
9 Correct 108 ms 15312 KB Output is correct
10 Correct 147 ms 16364 KB Output is correct
11 Correct 138 ms 16228 KB Output is correct
12 Correct 136 ms 16144 KB Output is correct
13 Correct 111 ms 13004 KB Output is correct
14 Correct 101 ms 12216 KB Output is correct
15 Correct 105 ms 12976 KB Output is correct
16 Correct 107 ms 12016 KB Output is correct
17 Correct 122 ms 13596 KB Output is correct
18 Correct 107 ms 12540 KB Output is correct
19 Correct 150 ms 15232 KB Output is correct
20 Correct 138 ms 15388 KB Output is correct
21 Correct 154 ms 16240 KB Output is correct
22 Correct 140 ms 15936 KB Output is correct
23 Correct 156 ms 15908 KB Output is correct
24 Correct 159 ms 15936 KB Output is correct
25 Correct 159 ms 16280 KB Output is correct
26 Correct 141 ms 15888 KB Output is correct
27 Correct 103 ms 16292 KB Output is correct
28 Correct 117 ms 16340 KB Output is correct
29 Correct 105 ms 16708 KB Output is correct
30 Correct 108 ms 16488 KB Output is correct
31 Correct 99 ms 16312 KB Output is correct
32 Execution timed out 3072 ms 16308 KB Time limit exceeded
33 Halted 0 ms 0 KB -