oj.uz

Submission #772890

# Submission time Handle Problem Language Result Execution time Memory
772890 2023-07-04T12:24:49 Z Valters07 Prize (CEOI22_prize) C++14
0 / 100
 446 ms 159144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+5;
const int LOG = log2(N)+2;
vector<int> g[N];
bool good[N];
int par[N][LOG], dis[N];
int tin[N], tout[N], tt;
int k;
vector<int> ve;
vector<pair<int,int> > qu;
void dfs(int u)
{
    good[u]=1;
    ve.pb(u);
    k--;
    tin[u]=++tt;
    for(int i = 1;i<LOG;i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:g[u])
    {
        if(k>0)
        {
            qu.pb({u,v});
            par[v][0]=u;
            dfs(v);
        }
    }
    tout[u]=tt;
}
void dfs2(int u)
{
    for(auto v:g[u])
        if(good[v])
            dis[v]+=dis[u],
            dfs2(v);
}
bool isanc(int u, int v)
{
    return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
int getlca(int u, int v)
{
    if(isanc(u,v))
        return u;
    if(isanc(v,u))
        return v;
    for(int i = LOG-1;i>=0;i--)
        if(!isanc(par[u][i],v))
            u=par[u][i];
    return par[u][0];
}
int getdist(int u, int v)
{
    int lca = getlca(u,v);
    return dis[u]+dis[v]-2*dis[lca];
}
int main()
{
    fio
//    ifstream cin("in.in");
    int n, q, t;
    cin >> n >> k >> q >> t;
    int r;
    for(int i = 1;i<=n;i++)
    {
        int p;
        cin >> p;
        if(p==-1)
            r=i;
        else
            g[p].pb(i);
    }
    for(int i = 1,p;i<=n;i++)
        cin >> p;
    par[r][0]=r;
    dfs(r);
    for(auto x:ve)
        cout << x << " ";
    cout << endl;
    assert(qu.size()<=q);
    for(auto x:qu)
        cout << "? " << x.fi << " " << x.se << endl;
    cout << "!" << endl;
    for(auto x:qu)
    {
        int x1, x2, x3, x4;
        cin >> x1 >> x2 >> x3 >> x4;
        dis[x.se]=x1+x2;
    }
    dfs2(r);
    for(int i = 0;i<t;i++)
    {
        int u, v;
        cin >> u >> v;
        int dist = getdist(u,v);
        cout << dist << " " << dist << endl;
    }
    cout << endl;
//    cin.close();
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:90:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     assert(qu.size()<=q);
      |            ~~~~~~~~~^~~
Main.cpp:100:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     dfs2(r);
      |     ~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 255 ms 93872 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 364 ms 96460 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 146 ms 42800 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 323 ms 67800 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 446 ms 159144 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -