oj.uz

Submission #781102

# Submission time Handle Problem Language Result Execution time Memory
781102 2023-07-12T17:55:33 Z Valters07 Prize (CEOI22_prize) C++14
100 / 100
 1811 ms 419284 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> g1[N], g2[N];
vector<pair<int,int> > wg[N][2];
int k;
int tin[N][2], tout[N][2], tt[2];
int par[N][LOG][2], dist[N][2];
bool chos[N];
vector<int> nodes;
vector<pair<int,int> > qu;
void dfs1(int u, int p)
{
    nodes.pb(u);
    k--;
    chos[u]=1;
    par[u][0][0]=p;
    tin[u][0]=++tt[0];
    for(int i = 1;i<LOG;i++)
        par[u][i][0]=par[par[u][i-1][0]][i-1][0];
    for(auto v:g1[u])
        if(k>0&&v!=p)
            dfs1(v,u);
    tout[u][0]=tt[0];
}
void dfs2(int u, int p)
{
    tin[u][1]=++tt[1];
    par[u][0][1]=p;
    for(int i = 1;i<LOG;i++)
        par[u][i][1]=par[par[u][i-1][1]][i-1][1];
    for(auto v:g2[u])
        if(v!=p)
            dfs2(v,u);
    tout[u][1]=tt[1];
}
bool isanc(int u, int v, int t)
{
    return (tin[u][t]<=tin[v][t]&&tout[v][t]<=tout[u][t]);
}
int getlca(int u, int v, int t)
{
    if(isanc(u,v,t))
        return u;
    if(isanc(v,u,t))
        return v;
    for(int i = LOG-1;i>=0;i--)
        if(!isanc(par[u][i][t],v,t))
            u=par[u][i][t];
    return par[u][0][t];
}
void calcq()
{
    sort(nodes.begin(),nodes.end(),[&](int &i, int &j){return (tin[i][1]<tin[j][1]);});
    for(int i = 1;i<nodes.size();i++)
        qu.pb({nodes[i-1],nodes[i]});
}
void addedge(int u, int v, int w, int t)
{
    wg[u][t].pb({v,w});
    wg[v][t].pb({u,-w});
}
void dfs3(int u, int t)
{
    for(auto v:wg[u][t])
    {
        int nwd = dist[u][t]+v.se;
        if(dist[v.fi][t]>nwd)
            dist[v.fi][t]=nwd,
            dfs3(v.fi,t);
    }
}
int getdist(int u, int v, int t)
{
    ll d1 = dist[u][t], d2 = dist[v][t];
    int lca = getlca(u,v,t);
    ll d3 = dist[lca][t];
    return d1+d2-d3*2;
}
int main()
{
    fio
//    ifstream cin("in.in");
    int n, q, t;
    cin >> n >> k >> q >> t;
    int r1, r2;
    for(int i = 1;i<=n;i++)
    {
        int p;
        cin >> p;
        if(p==-1)
            r1=i;
        else
            g1[p].pb(i);
    }
    for(int i = 1;i<=n;i++)
    {
        int p;
        cin >> p;
        if(p==-1)
            r2=i;
        else
            g2[p].pb(i);
    }
    dfs1(r1,r1);
    dfs2(r2,r2);
    calcq();
    for(auto x:nodes)
        cout << x << " ";
    cout << endl;
    for(auto x:qu)
        cout << "? " << x.fi << " " << x.se << "\n";
    cout << "!" << endl;
    r2=-1;
    for(auto x:qu)
    {
        int d11, d12, d21, d22;
        cin >> d11 >> d12 >> d21 >> d22;
        int lca1 = getlca(x.fi,x.se,0), lca2 = getlca(x.fi,x.se,1);
        addedge(lca1,x.fi,d11,0);
        addedge(lca1,x.se,d12,0);
        addedge(lca2,x.fi,d21,1);
        addedge(lca2,x.se,d22,1);
        if(r2==-1||tin[lca2][1]<tin[r2][1])
            r2=lca2;
    }
    for(int i = 1;i<=n;i++)
        dist[i][0]=dist[i][1]=2e9+5;
    dist[r1][0]=dist[r2][1]=0;
    dfs3(r1,0);
    dfs3(r2,1);
    vector<pair<int,int> > ans(t);
    for(int i = 0;i<t;i++)
    {
        int u, v;
        cin >> u >> v;
        ans[i]={getdist(u,v,0),getdist(u,v,1)};
    }
    for(auto x:ans)
        cout << x.fi << " " << x.se << "\n";
    return 0;
}

Compilation message

Main.cpp: In function 'void calcq()':
Main.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 1;i<nodes.size();i++)
      |                   ~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:140:9: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |     dfs3(r1,0);
      |     ~~~~^~~~~~
Main.cpp:116:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |     dfs2(r2,r2);
      |     ~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 259032 KB Output is correct
2 Correct 751 ms 261804 KB Output is correct
3 Correct 628 ms 213604 KB Output is correct
4 Correct 579 ms 213160 KB Output is correct
5 Correct 718 ms 215992 KB Output is correct
6 Correct 750 ms 224544 KB Output is correct
7 Correct 790 ms 224424 KB Output is correct
8 Correct 852 ms 223640 KB Output is correct
9 Correct 676 ms 213396 KB Output is correct
10 Correct 645 ms 215232 KB Output is correct
11 Correct 593 ms 211924 KB Output is correct
12 Correct 625 ms 214696 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 262032 KB Output is correct
2 Correct 748 ms 257780 KB Output is correct
3 Correct 686 ms 213572 KB Output is correct
4 Correct 673 ms 216116 KB Output is correct
5 Correct 686 ms 214544 KB Output is correct
6 Correct 946 ms 222304 KB Output is correct
7 Correct 998 ms 225536 KB Output is correct
8 Correct 1030 ms 225860 KB Output is correct
9 Correct 873 ms 223784 KB Output is correct
10 Correct 937 ms 224796 KB Output is correct
11 Correct 786 ms 220844 KB Output is correct
12 Correct 871 ms 224388 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 251632 KB Output is correct
2 Correct 582 ms 251836 KB Output is correct
3 Correct 448 ms 205228 KB Output is correct
4 Correct 459 ms 205216 KB Output is correct
5 Correct 468 ms 205212 KB Output is correct
6 Correct 563 ms 215108 KB Output is correct
7 Correct 540 ms 215148 KB Output is correct
8 Correct 518 ms 215216 KB Output is correct
9 Correct 572 ms 213020 KB Output is correct
10 Correct 651 ms 213008 KB Output is correct
11 Correct 576 ms 213036 KB Output is correct
12 Correct 622 ms 213116 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 409288 KB Output is correct
2 Correct 1356 ms 409308 KB Output is correct
3 Correct 979 ms 316468 KB Output is correct
4 Correct 1018 ms 316460 KB Output is correct
5 Correct 1012 ms 316448 KB Output is correct
6 Correct 1281 ms 336256 KB Output is correct
7 Correct 1312 ms 336304 KB Output is correct
8 Correct 1339 ms 336312 KB Output is correct
9 Correct 1250 ms 332044 KB Output is correct
10 Correct 1242 ms 332056 KB Output is correct
11 Correct 1269 ms 332044 KB Output is correct
12 Correct 1253 ms 332096 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1571 ms 419284 KB Output is correct
2 Correct 1481 ms 418784 KB Output is correct
3 Correct 1184 ms 323660 KB Output is correct
4 Correct 1235 ms 327844 KB Output is correct
5 Correct 1143 ms 322768 KB Output is correct
6 Correct 1811 ms 347528 KB Output is correct
7 Correct 1575 ms 343080 KB Output is correct
8 Correct 1719 ms 345732 KB Output is correct
9 Correct 1537 ms 340836 KB Output is correct
10 Correct 1572 ms 339612 KB Output is correct
11 Correct 1540 ms 339708 KB Output is correct
12 Correct 1620 ms 341868 KB Output is correct