oj.uz

Submission #1044152

# Submission time Handle Problem Language Result Execution time Memory
1044152 2024-08-05T07:39:25 Z 정희우(#11008) Prize (CEOI22_prize) C++17
100 / 100
 2063 ms 358912 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 213572 KB Output is correct
2 Correct 858 ms 215460 KB Output is correct
3 Correct 699 ms 186632 KB Output is correct
4 Correct 588 ms 185860 KB Output is correct
5 Correct 623 ms 185004 KB Output is correct
6 Correct 877 ms 190792 KB Output is correct
7 Correct 945 ms 190792 KB Output is correct
8 Correct 933 ms 188156 KB Output is correct
9 Correct 745 ms 185872 KB Output is correct
10 Correct 713 ms 186636 KB Output is correct
11 Correct 573 ms 183312 KB Output is correct
12 Correct 645 ms 183416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 215256 KB Output is correct
2 Correct 922 ms 213568 KB Output is correct
3 Correct 614 ms 183640 KB Output is correct
4 Correct 658 ms 183652 KB Output is correct
5 Correct 650 ms 185944 KB Output is correct
6 Correct 810 ms 189800 KB Output is correct
7 Correct 867 ms 189512 KB Output is correct
8 Correct 857 ms 190788 KB Output is correct
9 Correct 753 ms 188744 KB Output is correct
10 Correct 771 ms 188780 KB Output is correct
11 Correct 750 ms 191104 KB Output is correct
12 Correct 796 ms 190988 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 212416 KB Output is correct
2 Correct 683 ms 211812 KB Output is correct
3 Correct 566 ms 182128 KB Output is correct
4 Correct 522 ms 182208 KB Output is correct
5 Correct 615 ms 181952 KB Output is correct
6 Correct 649 ms 186284 KB Output is correct
7 Correct 548 ms 187228 KB Output is correct
8 Correct 563 ms 186820 KB Output is correct
9 Correct 513 ms 186700 KB Output is correct
10 Correct 616 ms 187576 KB Output is correct
11 Correct 555 ms 187604 KB Output is correct
12 Correct 565 ms 187544 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1737 ms 356612 KB Output is correct
2 Correct 1755 ms 355728 KB Output is correct
3 Correct 1243 ms 295756 KB Output is correct
4 Correct 1426 ms 295484 KB Output is correct
5 Correct 1345 ms 296428 KB Output is correct
6 Correct 1632 ms 305488 KB Output is correct
7 Correct 1530 ms 305492 KB Output is correct
8 Correct 1550 ms 305204 KB Output is correct
9 Correct 1474 ms 306500 KB Output is correct
10 Correct 1436 ms 306844 KB Output is correct
11 Correct 1348 ms 306952 KB Output is correct
12 Correct 1376 ms 306548 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2012 ms 358912 KB Output is correct
2 Correct 2063 ms 358700 KB Output is correct
3 Correct 1363 ms 298140 KB Output is correct
4 Correct 1422 ms 299188 KB Output is correct
5 Correct 1525 ms 298164 KB Output is correct
6 Correct 1982 ms 308076 KB Output is correct
7 Correct 1847 ms 307752 KB Output is correct
8 Correct 1885 ms 308136 KB Output is correct
9 Correct 1672 ms 308732 KB Output is correct
10 Correct 1816 ms 308840 KB Output is correct
11 Correct 1607 ms 309544 KB Output is correct
12 Correct 1677 ms 308828 KB Output is correct