oj.uz

Submission #1099185

# Submission time Handle Problem Language Result Execution time Memory
1099185 2024-10-10T17:09:40 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 1500 ms 18964 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>53)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 3 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 3 ms 4668 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 3 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 5976 KB Output is correct
3 Correct 119 ms 15484 KB Output is correct
4 Correct 97 ms 15384 KB Output is correct
5 Correct 104 ms 15476 KB Output is correct
6 Correct 90 ms 15468 KB Output is correct
7 Correct 92 ms 15572 KB Output is correct
8 Correct 94 ms 15716 KB Output is correct
9 Correct 89 ms 15368 KB Output is correct
10 Correct 100 ms 15488 KB Output is correct
11 Correct 102 ms 15260 KB Output is correct
12 Correct 96 ms 16096 KB Output is correct
13 Correct 91 ms 15716 KB Output is correct
14 Correct 93 ms 14600 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 18 ms 7768 KB Output is correct
3 Correct 30 ms 7800 KB Output is correct
4 Correct 75 ms 17128 KB Output is correct
5 Correct 76 ms 17392 KB Output is correct
6 Correct 75 ms 18320 KB Output is correct
7 Correct 70 ms 13500 KB Output is correct
8 Correct 69 ms 17884 KB Output is correct
9 Correct 73 ms 15048 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4708 KB Output is correct
2 Correct 11 ms 5752 KB Output is correct
3 Correct 77 ms 13444 KB Output is correct
4 Correct 122 ms 15324 KB Output is correct
5 Correct 91 ms 15316 KB Output is correct
6 Correct 103 ms 15504 KB Output is correct
7 Correct 97 ms 15576 KB Output is correct
8 Correct 98 ms 15520 KB Output is correct
9 Correct 121 ms 15528 KB Output is correct
10 Correct 99 ms 15640 KB Output is correct
11 Correct 99 ms 15208 KB Output is correct
12 Correct 104 ms 15492 KB Output is correct
13 Correct 100 ms 15572 KB Output is correct
14 Correct 92 ms 16276 KB Output is correct
15 Correct 108 ms 15304 KB Output is correct
16 Correct 102 ms 15352 KB Output is correct
17 Correct 97 ms 14852 KB Output is correct
18 Correct 99 ms 16512 KB Output is correct
19 Correct 98 ms 15436 KB Output is correct
20 Correct 94 ms 16488 KB Output is correct
21 Correct 98 ms 16680 KB Output is correct
22 Correct 101 ms 16612 KB Output is correct
23 Correct 101 ms 15556 KB Output is correct
24 Correct 86 ms 15680 KB Output is correct
25 Correct 101 ms 18964 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5976 KB Output is correct
2 Correct 15 ms 5976 KB Output is correct
3 Correct 112 ms 15812 KB Output is correct
4 Correct 132 ms 15628 KB Output is correct
5 Correct 152 ms 16868 KB Output is correct
6 Correct 153 ms 16380 KB Output is correct
7 Correct 158 ms 16912 KB Output is correct
8 Correct 157 ms 16868 KB Output is correct
9 Correct 106 ms 11828 KB Output is correct
10 Correct 127 ms 12016 KB Output is correct
11 Correct 117 ms 13744 KB Output is correct
12 Correct 159 ms 15220 KB Output is correct
13 Correct 132 ms 16268 KB Output is correct
14 Correct 155 ms 16232 KB Output is correct
15 Correct 149 ms 16632 KB Output is correct
16 Correct 124 ms 13312 KB Output is correct
17 Correct 103 ms 16300 KB Output is correct
18 Correct 95 ms 16344 KB Output is correct
19 Correct 90 ms 16256 KB Output is correct
20 Execution timed out 3081 ms 16428 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 6224 KB Output is correct
3 Partially correct 114 ms 15396 KB Output is partially correct
4 Correct 118 ms 15928 KB Output is correct
5 Partially correct 133 ms 15692 KB Output is partially correct
6 Partially correct 148 ms 16448 KB Output is partially correct
7 Correct 118 ms 15996 KB Output is correct
8 Correct 105 ms 15904 KB Output is correct
9 Correct 114 ms 16236 KB Output is correct
10 Partially correct 143 ms 16376 KB Output is partially correct
11 Correct 156 ms 16416 KB Output is correct
12 Correct 175 ms 16488 KB Output is correct
13 Correct 113 ms 13016 KB Output is correct
14 Correct 105 ms 12012 KB Output is correct
15 Correct 125 ms 13756 KB Output is correct
16 Correct 108 ms 12028 KB Output is correct
17 Correct 116 ms 13552 KB Output is correct
18 Correct 110 ms 12360 KB Output is correct
19 Correct 153 ms 15308 KB Output is correct
20 Correct 164 ms 15804 KB Output is correct
21 Partially correct 161 ms 16312 KB Output is partially correct
22 Correct 160 ms 16252 KB Output is correct
23 Correct 162 ms 16788 KB Output is correct
24 Correct 151 ms 16280 KB Output is correct
25 Correct 167 ms 16616 KB Output is correct
26 Correct 140 ms 16580 KB Output is correct
27 Correct 103 ms 16284 KB Output is correct
28 Correct 94 ms 16352 KB Output is correct
29 Correct 99 ms 16604 KB Output is correct
30 Correct 115 ms 16300 KB Output is correct
31 Correct 97 ms 16268 KB Output is correct
32 Execution timed out 3051 ms 16300 KB Time limit exceeded
33 Halted 0 ms 0 KB -