oj.uz

Submission #1099187

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

    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);
    }

    if(q>55)while(1);

    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 4696 KB Output is correct
8 Correct 3 ms 4672 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 5764 KB Output is correct
3 Correct 95 ms 15552 KB Output is correct
4 Correct 101 ms 15540 KB Output is correct
5 Correct 98 ms 15544 KB Output is correct
6 Correct 98 ms 15540 KB Output is correct
7 Correct 97 ms 15380 KB Output is correct
8 Correct 98 ms 15472 KB Output is correct
9 Correct 85 ms 15400 KB Output is correct
10 Correct 97 ms 15552 KB Output is correct
11 Correct 92 ms 15272 KB Output is correct
12 Correct 92 ms 15940 KB Output is correct
13 Correct 99 ms 15736 KB Output is correct
14 Correct 93 ms 14752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6232 KB Output is correct
2 Correct 17 ms 7852 KB Output is correct
3 Correct 28 ms 8048 KB Output is correct
4 Correct 92 ms 17280 KB Output is correct
5 Correct 68 ms 17204 KB Output is correct
6 Correct 74 ms 18316 KB Output is correct
7 Correct 69 ms 13524 KB Output is correct
8 Correct 69 ms 17884 KB Output is correct
9 Correct 72 ms 15052 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 75 ms 13364 KB Output is correct
4 Correct 102 ms 15376 KB Output is correct
5 Correct 101 ms 15564 KB Output is correct
6 Correct 123 ms 15536 KB Output is correct
7 Correct 99 ms 15468 KB Output is correct
8 Correct 104 ms 15472 KB Output is correct
9 Correct 108 ms 15924 KB Output is correct
10 Correct 96 ms 15456 KB Output is correct
11 Correct 106 ms 15408 KB Output is correct
12 Correct 119 ms 15396 KB Output is correct
13 Correct 111 ms 15084 KB Output is correct
14 Correct 97 ms 16288 KB Output is correct
15 Correct 117 ms 15480 KB Output is correct
16 Correct 113 ms 15560 KB Output is correct
17 Correct 94 ms 14844 KB Output is correct
18 Correct 93 ms 16228 KB Output is correct
19 Correct 99 ms 15468 KB Output is correct
20 Correct 99 ms 16408 KB Output is correct
21 Correct 115 ms 16372 KB Output is correct
22 Correct 104 ms 16564 KB Output is correct
23 Correct 105 ms 15604 KB Output is correct
24 Correct 87 ms 15756 KB Output is correct
25 Correct 108 ms 18948 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5976 KB Output is correct
2 Correct 14 ms 5976 KB Output is correct
3 Correct 123 ms 15660 KB Output is correct
4 Correct 144 ms 15716 KB Output is correct
5 Correct 179 ms 16848 KB Output is correct
6 Correct 159 ms 16416 KB Output is correct
7 Correct 152 ms 16888 KB Output is correct
8 Correct 166 ms 16828 KB Output is correct
9 Correct 111 ms 11840 KB Output is correct
10 Correct 95 ms 12540 KB Output is correct
11 Correct 107 ms 13528 KB Output is correct
12 Correct 148 ms 15208 KB Output is correct
13 Correct 133 ms 16280 KB Output is correct
14 Correct 144 ms 16224 KB Output is correct
15 Correct 150 ms 16808 KB Output is correct
16 Correct 123 ms 13424 KB Output is correct
17 Correct 103 ms 16140 KB Output is correct
18 Correct 113 ms 16476 KB Output is correct
19 Correct 96 ms 16360 KB Output is correct
20 Execution timed out 3010 ms 16408 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 5976 KB Output is correct
2 Correct 15 ms 5772 KB Output is correct
3 Partially correct 116 ms 15388 KB Output is partially correct
4 Correct 126 ms 16000 KB Output is correct
5 Partially correct 129 ms 15632 KB Output is partially correct
6 Partially correct 144 ms 16444 KB Output is partially correct
7 Correct 114 ms 15760 KB Output is correct
8 Correct 113 ms 15900 KB Output is correct
9 Correct 118 ms 16232 KB Output is correct
10 Partially correct 158 ms 16356 KB Output is partially correct
11 Correct 169 ms 16744 KB Output is correct
12 Correct 146 ms 16484 KB Output is correct
13 Correct 123 ms 13020 KB Output is correct
14 Correct 105 ms 12020 KB Output is correct
15 Correct 116 ms 13620 KB Output is correct
16 Correct 119 ms 12028 KB Output is correct
17 Correct 145 ms 13740 KB Output is correct
18 Correct 107 ms 12364 KB Output is correct
19 Correct 168 ms 15088 KB Output is correct
20 Correct 166 ms 15804 KB Output is correct
21 Partially correct 152 ms 16224 KB Output is partially correct
22 Correct 190 ms 16248 KB Output is correct
23 Correct 151 ms 16668 KB Output is correct
24 Correct 167 ms 16280 KB Output is correct
25 Correct 165 ms 16780 KB Output is correct
26 Correct 165 ms 16672 KB Output is correct
27 Correct 94 ms 16544 KB Output is correct
28 Correct 124 ms 16224 KB Output is correct
29 Correct 109 ms 16708 KB Output is correct
30 Correct 121 ms 16476 KB Output is correct
31 Correct 102 ms 16248 KB Output is correct
32 Execution timed out 3068 ms 16324 KB Time limit exceeded
33 Halted 0 ms 0 KB -