oj.uz

Submission #772888

# Submission time Handle Problem Language Result Execution time Memory
772888 2023-07-04T12:23:42 Z Valters07 Prize (CEOI22_prize) C++14
0 / 100
 452 ms 159172 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;
    for(auto x:qu)
        cout << "? " << x.fi << " " << x.se << "\n";
    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 << "\n";
    }
    cout << endl;
//    cin.close();
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:99:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     dfs2(r);
      |     ~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 228 ms 93868 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 241 ms 96508 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 156 ms 42776 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 286 ms 67812 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 452 ms 159172 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -