oj.uz

Submission #1099208

# Submission time Handle Problem Language Result Execution time Memory
1099208 2024-10-10T18:12:27 Z MMihalev Highway Tolls (IOI18_highway) C++14
51 / 100
 1500 ms 20332 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>45)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 5720 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 2 ms 5760 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 1 ms 5720 KB Output is correct
7 Correct 1 ms 5720 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 5720 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 10 ms 5640 KB Output is correct
3 Correct 104 ms 15024 KB Output is correct
4 Correct 109 ms 14520 KB Output is correct
5 Correct 96 ms 15160 KB Output is correct
6 Correct 116 ms 16292 KB Output is correct
7 Correct 83 ms 14608 KB Output is correct
8 Correct 92 ms 14360 KB Output is correct
9 Correct 100 ms 14332 KB Output is correct
10 Correct 110 ms 15260 KB Output is correct
11 Correct 87 ms 14756 KB Output is correct
12 Correct 97 ms 16096 KB Output is correct
13 Correct 89 ms 15232 KB Output is correct
14 Correct 99 ms 14980 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 18 ms 8492 KB Output is correct
3 Correct 28 ms 7596 KB Output is correct
4 Correct 100 ms 17008 KB Output is correct
5 Correct 74 ms 16700 KB Output is correct
6 Correct 82 ms 18552 KB Output is correct
7 Correct 74 ms 13584 KB Output is correct
8 Correct 82 ms 17596 KB Output is correct
9 Correct 81 ms 14604 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 13 ms 5688 KB Output is correct
3 Correct 80 ms 12148 KB Output is correct
4 Correct 114 ms 14528 KB Output is correct
5 Correct 106 ms 14396 KB Output is correct
6 Correct 106 ms 14400 KB Output is correct
7 Correct 83 ms 14400 KB Output is correct
8 Correct 90 ms 14144 KB Output is correct
9 Correct 107 ms 15260 KB Output is correct
10 Correct 107 ms 15212 KB Output is correct
11 Correct 111 ms 14216 KB Output is correct
12 Correct 101 ms 15832 KB Output is correct
13 Correct 96 ms 14948 KB Output is correct
14 Correct 105 ms 15236 KB Output is correct
15 Correct 99 ms 14396 KB Output is correct
16 Correct 88 ms 14328 KB Output is correct
17 Correct 86 ms 15192 KB Output is correct
18 Correct 92 ms 15528 KB Output is correct
19 Correct 87 ms 14280 KB Output is correct
20 Correct 84 ms 15244 KB Output is correct
21 Correct 116 ms 16816 KB Output is correct
22 Correct 105 ms 16824 KB Output is correct
23 Correct 100 ms 16512 KB Output is correct
24 Correct 108 ms 16964 KB Output is correct
25 Correct 103 ms 20332 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6664 KB Output is correct
2 Correct 12 ms 6920 KB Output is correct
3 Correct 119 ms 15580 KB Output is correct
4 Correct 134 ms 16008 KB Output is correct
5 Correct 150 ms 16384 KB Output is correct
6 Correct 140 ms 17528 KB Output is correct
7 Correct 153 ms 16780 KB Output is correct
8 Correct 152 ms 17652 KB Output is correct
9 Correct 115 ms 13076 KB Output is correct
10 Correct 103 ms 12780 KB Output is correct
11 Correct 128 ms 14436 KB Output is correct
12 Correct 154 ms 15132 KB Output is correct
13 Correct 138 ms 15904 KB Output is correct
14 Execution timed out 3018 ms 16524 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6664 KB Output is correct
2 Correct 13 ms 6804 KB Output is correct
3 Correct 106 ms 15020 KB Output is correct
4 Correct 122 ms 16496 KB Output is correct
5 Correct 121 ms 16072 KB Output is correct
6 Correct 139 ms 16896 KB Output is correct
7 Correct 118 ms 15204 KB Output is correct
8 Correct 108 ms 15132 KB Output is correct
9 Correct 120 ms 15324 KB Output is correct
10 Correct 154 ms 16672 KB Output is correct
11 Correct 137 ms 16720 KB Output is correct
12 Correct 155 ms 16356 KB Output is correct
13 Correct 115 ms 13584 KB Output is correct
14 Correct 118 ms 13556 KB Output is correct
15 Correct 111 ms 13540 KB Output is correct
16 Correct 119 ms 12788 KB Output is correct
17 Correct 119 ms 14432 KB Output is correct
18 Correct 109 ms 13260 KB Output is correct
19 Correct 155 ms 15696 KB Output is correct
20 Correct 126 ms 15412 KB Output is correct
21 Correct 145 ms 16316 KB Output is correct
22 Execution timed out 3086 ms 16420 KB Time limit exceeded
23 Halted 0 ms 0 KB -