oj.uz

Submission #1098732

# Submission time Handle Problem Language Result Execution time Memory
1098732 2024-10-09T19:33:59 Z MMihalev Highway Tolls (IOI18_highway) C++14
18 / 100
 1500 ms 262144 KB 
#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N=90005;
int n,m;
vector<int>w;
vector<pair<int,int> >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;
int q;
void initdfs(int u,int par)
{
    parent[u]=par;
    for(auto [v,edge] : g[u])
    {
        if(v==par)continue;
        depth[v]=depth[u]+1;
        paredge[v]=edge;
        initdfs(v,u);
    }
}
int onpath(int l,int r)
{
    if(l==r)return l;
    int mid=(l+r)/2;

    for(int u=l;u<=mid;u++)
    {
        for(auto [v,edge]:g[u])
        {
            w[edge]=1;
        }
    }
    long long ncost=ask(w);q++;
    for(int u=l;u<=mid;u++)
    {
        for(auto [v,edge]:g[u])
        {
            w[edge]=0;
        }
    }

    if(ncost>cost)
    {
        return onpath(l,mid);
    }
    return onpath(mid+1,r);
}
void markdfs(int u,bool f)
{
    w[paredge[u]]=f;
    for(auto [v,edge]:g[u])
    {
        if(v==parent[u])continue;
        markdfs(v,f);
    }
}
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 l,int r)
{
    nodes.clear();
    for(int i=l;i<=r;i++)
    {
        nodesdfs(g[root][i].first);
    }
    sort(nodes.rbegin(),nodes.rend());
    ENDS.push_back(rec(0,nodes.size()-1));
}
void solvetwo(int l,int r)
{
    int mid=(l+r)/2;

    for(int i=l;i<=mid;i++)
    {
        markdfs(g[root][i].first,1);
    }
    long long ncost=ask(w);q++;
    for(int i=l;i<=mid;i++)
    {
        markdfs(g[root][i].first,0);
    }

    if(ncost==cost)solvetwo(mid+1,r);
    else if(ncost==b*edges)solvetwo(l,mid);
    else
    {
        solve(l,mid);
        solve(mid+1,r);
    }
}
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);
    edges=cost/a;

    root=onpath(0,n-1);
    initdfs(root,-1);

    bool twodifferent=0;

    for(int i=0;i<g[root].size();i++)
    {
        w[g[root][i].second]=1;
    }
    long long ncost=ask(w);q++;
    if((ncost-cost)==2*(b-a))twodifferent=1;
    for(int i=0;i<g[root].size();i++)
    {
        w[g[root][i].second]=0;
    }

    if(!twodifferent)
    {
        ENDS.push_back(root);
        solve(0,g[root].size()-1);
    }
    else
    {
        solvetwo(0,g[root].size()-1);
    }

    if(q>50)while(1);

    answer(ENDS[0],ENDS[1]);
}

Compilation message

highway.cpp: In function 'void initdfs(int, int)':
highway.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [v,edge] : g[u])
      |              ^
highway.cpp: In function 'int onpath(int, int)':
highway.cpp:37:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         for(auto [v,edge]:g[u])
      |                  ^
highway.cpp:45:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         for(auto [v,edge]:g[u])
      |                  ^
highway.cpp: In function 'void markdfs(int, bool)':
highway.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void nodesdfs(int)':
highway.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [v,edge]:g[u])
      |              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:152: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]
  152 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~
highway.cpp:158: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]
  158 |     for(int i=0;i<g[root].size();i++)
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 2512 KB Output is correct
8 Correct 2 ms 2344 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 10 ms 3416 KB Output is correct
3 Correct 101 ms 9856 KB Output is correct
4 Correct 95 ms 9756 KB Output is correct
5 Correct 92 ms 9852 KB Output is correct
6 Correct 85 ms 9804 KB Output is correct
7 Correct 102 ms 9844 KB Output is correct
8 Correct 92 ms 10100 KB Output is correct
9 Correct 93 ms 9928 KB Output is correct
10 Correct 88 ms 9848 KB Output is correct
11 Correct 101 ms 10664 KB Output is correct
12 Correct 98 ms 11216 KB Output is correct
13 Correct 85 ms 10828 KB Output is correct
14 Correct 94 ms 10240 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3672 KB Output is correct
2 Correct 18 ms 5208 KB Output is correct
3 Correct 22 ms 6352 KB Output is correct
4 Correct 71 ms 12812 KB Output is correct
5 Correct 67 ms 12808 KB Output is correct
6 Correct 70 ms 13600 KB Output is correct
7 Correct 77 ms 14608 KB Output is correct
8 Correct 71 ms 13124 KB Output is correct
9 Correct 75 ms 13336 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 9 ms 3160 KB Output is correct
3 Correct 70 ms 8520 KB Output is correct
4 Correct 90 ms 9844 KB Output is correct
5 Correct 95 ms 9716 KB Output is correct
6 Correct 102 ms 9696 KB Output is correct
7 Correct 92 ms 9756 KB Output is correct
8 Correct 91 ms 9672 KB Output is correct
9 Correct 118 ms 9848 KB Output is correct
10 Correct 96 ms 9884 KB Output is correct
11 Correct 94 ms 10300 KB Output is correct
12 Correct 112 ms 10336 KB Output is correct
13 Correct 99 ms 10044 KB Output is correct
14 Correct 94 ms 11096 KB Output is correct
15 Correct 103 ms 9812 KB Output is correct
16 Correct 84 ms 9672 KB Output is correct
17 Correct 97 ms 9952 KB Output is correct
18 Correct 96 ms 11104 KB Output is correct
19 Correct 87 ms 9856 KB Output is correct
20 Correct 90 ms 11332 KB Output is correct
21 Execution timed out 3022 ms 9760 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -