oj.uz

Submission #1099182

# Submission time Handle Problem Language Result Execution time Memory
1099182 2024-10-10T17:03:54 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 180 ms 18880 KB 
#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N=90005;
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;
int q;
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);
        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)
{
    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);
        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);
    edges=cost/a;

    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
    {
        solve(branch,0);
    }

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

Compilation message

highway.cpp: In function 'void initbfs()':
highway.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for(auto [v,edge]:G[u])
      |                  ^
highway.cpp: In function 'int onpath()':
highway.cpp:58:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |             for(auto [v,edge]:G[u])
      |                      ^
highway.cpp:66:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |             for(auto [v,edge]:G[u])
      |                      ^
highway.cpp: In function 'void nodesdfs(int)':
highway.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void solve(int, bool)':
highway.cpp:116: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]
  116 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp: In function 'int onpath()':
highway.cpp:79:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     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 4512 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 11 ms 5976 KB Output is correct
3 Correct 97 ms 15384 KB Output is correct
4 Correct 105 ms 15468 KB Output is correct
5 Correct 96 ms 15480 KB Output is correct
6 Correct 95 ms 15544 KB Output is correct
7 Correct 103 ms 15380 KB Output is correct
8 Correct 109 ms 15380 KB Output is correct
9 Correct 95 ms 15472 KB Output is correct
10 Correct 108 ms 15648 KB Output is correct
11 Correct 96 ms 15256 KB Output is correct
12 Correct 101 ms 16124 KB Output is correct
13 Correct 96 ms 15908 KB Output is correct
14 Correct 98 ms 14720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6488 KB Output is correct
2 Correct 17 ms 7876 KB Output is correct
3 Correct 25 ms 7700 KB Output is correct
4 Correct 73 ms 17260 KB Output is correct
5 Correct 72 ms 17280 KB Output is correct
6 Correct 69 ms 18496 KB Output is correct
7 Correct 72 ms 13580 KB Output is correct
8 Correct 70 ms 17696 KB Output is correct
9 Correct 84 ms 14820 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 5760 KB Output is correct
3 Correct 68 ms 13336 KB Output is correct
4 Correct 106 ms 15540 KB Output is correct
5 Correct 93 ms 15384 KB Output is correct
6 Correct 112 ms 15512 KB Output is correct
7 Correct 99 ms 15536 KB Output is correct
8 Correct 96 ms 15348 KB Output is correct
9 Correct 116 ms 15544 KB Output is correct
10 Correct 94 ms 15540 KB Output is correct
11 Correct 111 ms 15356 KB Output is correct
12 Correct 101 ms 15412 KB Output is correct
13 Correct 94 ms 15148 KB Output is correct
14 Correct 93 ms 16248 KB Output is correct
15 Correct 94 ms 15504 KB Output is correct
16 Correct 108 ms 15396 KB Output is correct
17 Correct 99 ms 14856 KB Output is correct
18 Correct 112 ms 16160 KB Output is correct
19 Correct 99 ms 15524 KB Output is correct
20 Correct 112 ms 16472 KB Output is correct
21 Correct 99 ms 16540 KB Output is correct
22 Correct 94 ms 16612 KB Output is correct
23 Correct 86 ms 15536 KB Output is correct
24 Correct 97 ms 15756 KB Output is correct
25 Correct 101 ms 18880 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5976 KB Output is correct
2 Correct 15 ms 5976 KB Output is correct
3 Correct 119 ms 16064 KB Output is correct
4 Correct 131 ms 15644 KB Output is correct
5 Correct 154 ms 16864 KB Output is correct
6 Correct 163 ms 16372 KB Output is correct
7 Correct 150 ms 16776 KB Output is correct
8 Correct 151 ms 16900 KB Output is correct
9 Correct 111 ms 11824 KB Output is correct
10 Correct 110 ms 12008 KB Output is correct
11 Correct 115 ms 13516 KB Output is correct
12 Correct 149 ms 15212 KB Output is correct
13 Correct 129 ms 16224 KB Output is correct
14 Correct 156 ms 16228 KB Output is correct
15 Correct 166 ms 16560 KB Output is correct
16 Correct 138 ms 13340 KB Output is correct
17 Correct 94 ms 16240 KB Output is correct
18 Correct 98 ms 16336 KB Output is correct
19 Correct 95 ms 16552 KB Output is correct
20 Incorrect 115 ms 16480 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5796 KB Output is correct
2 Correct 14 ms 5976 KB Output is correct
3 Partially correct 139 ms 15400 KB Output is partially correct
4 Correct 121 ms 15936 KB Output is correct
5 Partially correct 153 ms 15708 KB Output is partially correct
6 Partially correct 151 ms 16456 KB Output is partially correct
7 Correct 110 ms 15748 KB Output is correct
8 Correct 108 ms 15812 KB Output is correct
9 Correct 121 ms 16208 KB Output is correct
10 Partially correct 140 ms 16368 KB Output is partially correct
11 Correct 152 ms 16384 KB Output is correct
12 Correct 142 ms 16480 KB Output is correct
13 Correct 111 ms 12984 KB Output is correct
14 Correct 112 ms 12012 KB Output is correct
15 Correct 123 ms 13684 KB Output is correct
16 Correct 108 ms 12016 KB Output is correct
17 Correct 136 ms 13560 KB Output is correct
18 Correct 110 ms 12392 KB Output is correct
19 Correct 176 ms 15252 KB Output is correct
20 Correct 152 ms 15820 KB Output is correct
21 Partially correct 161 ms 16308 KB Output is partially correct
22 Correct 163 ms 16236 KB Output is correct
23 Correct 173 ms 16760 KB Output is correct
24 Correct 169 ms 16716 KB Output is correct
25 Correct 180 ms 16584 KB Output is correct
26 Correct 157 ms 16788 KB Output is correct
27 Correct 96 ms 16368 KB Output is correct
28 Correct 114 ms 16492 KB Output is correct
29 Correct 110 ms 16612 KB Output is correct
30 Correct 104 ms 16440 KB Output is correct
31 Correct 98 ms 16312 KB Output is correct
32 Incorrect 98 ms 16308 KB Output isn't correct
33 Halted 0 ms 0 KB -