oj.uz

Submission #1099210

# Submission time Handle Problem Language Result Execution time Memory
1099210 2024-10-10T18:13:58 Z MMihalev Highway Tolls (IOI18_highway) C++14
82 / 100
 1500 ms 20464 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()
{
    vector<pair<int,int>>node;
    for(int i=0;i<n;i++)
    {
        node.push_back({G[i].size(),i});
    }
    sort(node.begin(),node.end());
 
    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[node[u].second])
            {
                w[edge]=1;
            }
        }
        long long ncost=ask(w);q++;
        for(int u=0;u<=mid;u++)
        {
            for(auto [v,edge]:G[node[u].second])
            {
                w[edge]=0;
            }
        }
        if(ncost!=cost)
        {
            ans=node[mid].second;
            r=mid-1;
        }
        else l=mid+1;
    }
 
    return ans;
}
void nodesdfs(int u)
{
    if(remedges==edges)
    {
        if(depth[u]<=remedges)nodes.push_back({depth[u],u});
    }
    else if(depth[u]==remedges)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>46)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:66:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |             for(auto [v,edge]:G[node[u].second])
      |                      ^
highway.cpp:74:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |             for(auto [v,edge]:G[node[u].second])
      |                      ^
highway.cpp: In function 'void nodesdfs(int)':
highway.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void solve(int, bool)':
highway.cpp:129: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]
  129 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp: In function 'int onpath()':
highway.cpp:87:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     return ans;
      |            ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 5720 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 2 ms 5720 KB Output is correct
11 Correct 2 ms 5720 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 10 ms 6664 KB Output is correct
3 Correct 99 ms 15100 KB Output is correct
4 Correct 106 ms 14308 KB Output is correct
5 Correct 104 ms 15136 KB Output is correct
6 Correct 100 ms 16012 KB Output is correct
7 Correct 89 ms 14652 KB Output is correct
8 Correct 96 ms 14364 KB Output is correct
9 Correct 103 ms 14316 KB Output is correct
10 Correct 102 ms 15284 KB Output is correct
11 Correct 105 ms 14756 KB Output is correct
12 Correct 93 ms 16044 KB Output is correct
13 Correct 104 ms 15248 KB Output is correct
14 Correct 96 ms 15024 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6920 KB Output is correct
2 Correct 19 ms 7476 KB Output is correct
3 Correct 27 ms 8368 KB Output is correct
4 Correct 83 ms 17080 KB Output is correct
5 Correct 95 ms 16824 KB Output is correct
6 Correct 82 ms 18680 KB Output is correct
7 Correct 92 ms 13524 KB Output is correct
8 Correct 79 ms 17596 KB Output is correct
9 Correct 94 ms 14608 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 11 ms 5824 KB Output is correct
3 Correct 78 ms 12056 KB Output is correct
4 Correct 98 ms 14792 KB Output is correct
5 Correct 101 ms 14340 KB Output is correct
6 Correct 86 ms 14324 KB Output is correct
7 Correct 85 ms 14340 KB Output is correct
8 Correct 97 ms 14348 KB Output is correct
9 Correct 98 ms 15156 KB Output is correct
10 Correct 93 ms 15212 KB Output is correct
11 Correct 102 ms 14228 KB Output is correct
12 Correct 106 ms 15816 KB Output is correct
13 Correct 95 ms 14964 KB Output is correct
14 Correct 94 ms 15240 KB Output is correct
15 Correct 96 ms 14308 KB Output is correct
16 Correct 92 ms 14324 KB Output is correct
17 Correct 90 ms 15008 KB Output is correct
18 Correct 93 ms 15528 KB Output is correct
19 Correct 85 ms 14296 KB Output is correct
20 Correct 84 ms 15252 KB Output is correct
21 Correct 104 ms 16716 KB Output is correct
22 Correct 100 ms 16820 KB Output is correct
23 Correct 99 ms 16612 KB Output is correct
24 Correct 111 ms 17092 KB Output is correct
25 Correct 107 ms 20464 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6664 KB Output is correct
2 Correct 12 ms 6920 KB Output is correct
3 Correct 113 ms 15580 KB Output is correct
4 Correct 139 ms 15928 KB Output is correct
5 Correct 155 ms 16396 KB Output is correct
6 Correct 138 ms 17532 KB Output is correct
7 Correct 159 ms 16800 KB Output is correct
8 Correct 170 ms 17500 KB Output is correct
9 Correct 137 ms 13024 KB Output is correct
10 Correct 101 ms 12820 KB Output is correct
11 Correct 115 ms 14428 KB Output is correct
12 Correct 154 ms 15564 KB Output is correct
13 Correct 126 ms 15852 KB Output is correct
14 Execution timed out 3086 ms 16800 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6664 KB Output is correct
2 Correct 14 ms 5896 KB Output is correct
3 Correct 109 ms 15016 KB Output is correct
4 Correct 131 ms 16732 KB Output is correct
5 Correct 122 ms 16064 KB Output is correct
6 Correct 153 ms 17072 KB Output is correct
7 Correct 115 ms 15220 KB Output is correct
8 Correct 106 ms 15144 KB Output is correct
9 Correct 119 ms 15332 KB Output is correct
10 Correct 146 ms 16664 KB Output is correct
11 Correct 141 ms 16700 KB Output is correct
12 Correct 159 ms 16364 KB Output is correct
13 Correct 102 ms 13572 KB Output is correct
14 Correct 106 ms 13272 KB Output is correct
15 Correct 101 ms 13808 KB Output is correct
16 Correct 98 ms 12780 KB Output is correct
17 Correct 118 ms 14420 KB Output is correct
18 Correct 109 ms 13252 KB Output is correct
19 Correct 150 ms 15708 KB Output is correct
20 Correct 128 ms 15628 KB Output is correct
21 Correct 135 ms 16108 KB Output is correct
22 Correct 159 ms 16420 KB Output is correct
23 Correct 147 ms 16544 KB Output is correct
24 Correct 133 ms 16048 KB Output is correct
25 Correct 162 ms 16432 KB Output is correct
26 Correct 157 ms 16732 KB Output is correct
27 Correct 117 ms 17072 KB Output is correct
28 Correct 91 ms 16936 KB Output is correct
29 Correct 104 ms 17284 KB Output is correct
30 Correct 103 ms 17084 KB Output is correct
31 Correct 88 ms 17052 KB Output is correct
32 Correct 113 ms 16928 KB Output is correct
33 Correct 94 ms 17340 KB Output is correct
34 Correct 91 ms 16896 KB Output is correct
35 Correct 98 ms 16888 KB Output is correct
36 Correct 106 ms 16852 KB Output is correct
37 Correct 108 ms 17220 KB Output is correct
38 Correct 106 ms 17044 KB Output is correct
39 Correct 156 ms 16480 KB Output is correct
40 Correct 136 ms 16832 KB Output is correct
41 Correct 146 ms 16168 KB Output is correct
42 Correct 138 ms 16124 KB Output is correct