oj.uz

Submission #1044139

# Submission time Handle Problem Language Result Execution time Memory
1044139 2024-08-05T07:34:18 Z 정희우(#11008) Prize (CEOI22_prize) C++17
0 / 100
 2049 ms 359444 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=1000010;
const int MAX_Q=100010;
const int BN=20;

int n,k,q1,q2;
vint edge[2][MAX_N];
int root[2];
int depth[2][MAX_N];
int ac[2][MAX_N][BN];
vint vert;
int idx[MAX_N];
lint dist[2][MAX_N];
lint ans[2][MAX_Q];

void fillac(int v,int p,int t)
{
    depth[t][v]=depth[t][p]+1;
    ac[t][v][0]=p;
    for(int i=1;i<BN;i++)
        ac[t][v][i]=ac[t][ac[t][v][i-1]][i-1];
    for(auto v0 : edge[t][v])
        if(v0!=p)
            fillac(v0,v,t);
}

void dfs(int v,int p,int t,int &c)
{
    if(t)
        idx[v]=c++;
    else if(vert.size()==k)
        return;
    else
        vert.push_back(v);
    for(auto v0 : edge[t][v])
        if(v0!=p)
            dfs(v0,v,t,c);
}

int lca(int u,int v,int t)
{
    if(depth[t][u]>depth[t][v])swap(u,v);
    for(int i=BN-1;i>=0;i--)
        if(depth[t][ac[t][v][i]]>=depth[t][u])
            v=ac[t][v][i];
    if(u==v)return v;
    for(int i=BN-1;i>=0;i--)
        if(ac[t][v][i]==ac[t][u][i])
        {
            v=ac[t][v][i];
            u=ac[t][u][i];
        }
    return ac[t][v][0];
}

bool comp(const int &i,const int &j)
{
    return idx[i]<idx[j];
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> k >> q1 >> q2;
    for(int t=0;t<2;t++)
        for(int i=1;i<=n;i++)
        {
            int p;
            cin >> p;
            if(p==-1)
            {
                root[t]=i;
                continue;
            }
            edge[t][i].push_back(p);
            edge[t][p].push_back(i);
        }
    for(int t=0;t<2;t++)
    {
        int c=0;
        fillac(root[t],root[t],t);
        dfs(root[1],root[1],t,c);
    }
    sort(vert.begin(),vert.end(),comp);
    for(auto v : vert)
        cout << v << ' ';
    cout << '\n';
    for(int i=0;i<k-1;i++)
        cout << "? " << vert[i] << ' ' << vert[i+1] << '\n';
    cout << "!\n" << flush;
    for(int i=0;i<k-1;i++)
    {
        lint dup,ddown;
        int u=vert[i],v=vert[i+1];
        for(int t=0;t<2;t++)
        {
            cin >> dup >> ddown;
            int l=lca(u,v,t);
            dist[t][l]=dist[t][u]-dup;
            dist[t][v]=dist[t][u]-dup+ddown;
        }
    }
    for(int i=0;i<q2;i++)
    {
        int u,v;
        cin >> u >> v;
        for(int t=0;t<2;t++)
        {
            int l=lca(u,v,t);
            ans[t][i]=dist[t][u]+dist[t][v]-dist[t][l]*2;
        }
    }
    for(int i=0;i<q2;i++)
        cout << ans[0][i] << ' ' << ans[1][i] << '\n';
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int, int, int&)':
Main.cpp:39:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     else if(vert.size()==k)
      |             ~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 214368 KB Output is correct
2 Correct 911 ms 215388 KB Output is correct
3 Runtime error 576 ms 185908 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1185 ms 215216 KB Output is correct
2 Correct 1069 ms 213568 KB Output is correct
3 Runtime error 782 ms 183312 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 212924 KB Output is correct
2 Correct 728 ms 211948 KB Output is correct
3 Runtime error 450 ms 181960 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 349032 KB Output is correct
2 Correct 1912 ms 356204 KB Output is correct
3 Runtime error 1112 ms 295340 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2049 ms 359284 KB Output is correct
2 Correct 2033 ms 359444 KB Output is correct
3 Runtime error 1296 ms 298024 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -