oj.uz

Submission #1099190

# Submission time Handle Problem Language Result Execution time Memory
1099190 2024-10-10T17:14:02 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 194 ms 18940 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>57)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 3 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 2 ms 4696 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 2 ms 4468 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 2 ms 4612 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 109 ms 15484 KB Output is correct
4 Correct 102 ms 15376 KB Output is correct
5 Correct 101 ms 15476 KB Output is correct
6 Correct 110 ms 15480 KB Output is correct
7 Correct 95 ms 15548 KB Output is correct
8 Correct 121 ms 15468 KB Output is correct
9 Correct 98 ms 15468 KB Output is correct
10 Correct 95 ms 15376 KB Output is correct
11 Correct 87 ms 15136 KB Output is correct
12 Correct 95 ms 16084 KB Output is correct
13 Correct 89 ms 15916 KB Output is correct
14 Correct 95 ms 14724 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 7736 KB Output is correct
3 Correct 25 ms 7704 KB Output is correct
4 Correct 76 ms 17232 KB Output is correct
5 Correct 74 ms 17436 KB Output is correct
6 Correct 75 ms 18316 KB Output is correct
7 Correct 75 ms 13492 KB Output is correct
8 Correct 78 ms 17716 KB Output is correct
9 Correct 75 ms 14824 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 12 ms 5776 KB Output is correct
3 Correct 98 ms 13356 KB Output is correct
4 Correct 113 ms 15528 KB Output is correct
5 Correct 98 ms 15468 KB Output is correct
6 Correct 104 ms 15340 KB Output is correct
7 Correct 107 ms 15480 KB Output is correct
8 Correct 112 ms 15448 KB Output is correct
9 Correct 105 ms 15516 KB Output is correct
10 Correct 98 ms 15348 KB Output is correct
11 Correct 107 ms 15264 KB Output is correct
12 Correct 99 ms 15452 KB Output is correct
13 Correct 105 ms 15104 KB Output is correct
14 Correct 112 ms 16128 KB Output is correct
15 Correct 105 ms 15476 KB Output is correct
16 Correct 100 ms 15344 KB Output is correct
17 Correct 95 ms 14852 KB Output is correct
18 Correct 87 ms 16100 KB Output is correct
19 Correct 99 ms 15536 KB Output is correct
20 Correct 94 ms 16448 KB Output is correct
21 Correct 95 ms 16444 KB Output is correct
22 Correct 97 ms 16400 KB Output is correct
23 Correct 91 ms 15520 KB Output is correct
24 Correct 91 ms 15752 KB Output is correct
25 Correct 103 ms 18940 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 15 ms 5976 KB Output is correct
3 Correct 109 ms 15724 KB Output is correct
4 Correct 136 ms 15856 KB Output is correct
5 Correct 153 ms 16984 KB Output is correct
6 Correct 184 ms 16728 KB Output is correct
7 Correct 175 ms 16952 KB Output is correct
8 Correct 152 ms 16940 KB Output is correct
9 Correct 116 ms 12296 KB Output is correct
10 Correct 106 ms 12004 KB Output is correct
11 Correct 123 ms 13740 KB Output is correct
12 Correct 155 ms 15212 KB Output is correct
13 Correct 170 ms 16336 KB Output is correct
14 Correct 164 ms 16220 KB Output is correct
15 Correct 163 ms 16804 KB Output is correct
16 Correct 131 ms 13412 KB Output is correct
17 Correct 94 ms 16176 KB Output is correct
18 Correct 97 ms 16340 KB Output is correct
19 Correct 105 ms 16236 KB Output is correct
20 Incorrect 103 ms 16560 KB Output isn't correct
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 13 ms 5976 KB Output is correct
3 Partially correct 115 ms 15400 KB Output is partially correct
4 Correct 119 ms 15968 KB Output is correct
5 Partially correct 131 ms 15576 KB Output is partially correct
6 Partially correct 159 ms 16444 KB Output is partially correct
7 Correct 127 ms 15748 KB Output is correct
8 Correct 131 ms 15792 KB Output is correct
9 Correct 136 ms 16168 KB Output is correct
10 Partially correct 159 ms 16452 KB Output is partially correct
11 Correct 194 ms 16384 KB Output is correct
12 Correct 150 ms 16472 KB Output is correct
13 Correct 118 ms 13196 KB Output is correct
14 Correct 103 ms 12016 KB Output is correct
15 Correct 124 ms 13712 KB Output is correct
16 Correct 116 ms 12004 KB Output is correct
17 Correct 119 ms 13744 KB Output is correct
18 Correct 105 ms 12352 KB Output is correct
19 Correct 160 ms 15300 KB Output is correct
20 Correct 183 ms 15940 KB Output is correct
21 Partially correct 161 ms 16224 KB Output is partially correct
22 Correct 166 ms 16232 KB Output is correct
23 Correct 158 ms 16628 KB Output is correct
24 Correct 180 ms 16272 KB Output is correct
25 Correct 169 ms 16756 KB Output is correct
26 Correct 160 ms 16676 KB Output is correct
27 Correct 98 ms 16340 KB Output is correct
28 Correct 96 ms 16364 KB Output is correct
29 Correct 104 ms 16580 KB Output is correct
30 Correct 124 ms 16392 KB Output is correct
31 Correct 99 ms 16304 KB Output is correct
32 Incorrect 107 ms 16260 KB Output isn't correct
33 Halted 0 ms 0 KB -