Submission #781102

#	Time	Username	Problem	Language	Result	Execution time	Memory
781102		Valters07	Prize (CEOI22_prize)	C++14	100 / 100	1811 ms	419284 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24