oj.uz

Submission #993513

# Submission time Handle Problem Language Result Execution time Memory
993513 2024-06-05T22:09:05 Z Savu_Stefan_Catalin Prize (CEOI22_prize) C++14
100 / 100
 2308 ms 637748 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int NMAX=1e6+505;
int cnt,ine[2][NMAX+5],lv[2][NMAX+5],n,t[2][NMAX+5],cen[2],invine[2][NMAX+5],k,q,T,id[NMAX+5],dp[NMAX+5],rmq[2][25][NMAX+5],imp[NMAX+5],invid[NMAX+5],rr[2][NMAX+5];
vector <int> v[2][NMAX+5];
pair<pair<int,int>,pair<int,int>> ras[NMAX+5];
int sz[NMAX+5],ap[NMAX+5],tt[NMAX+5],tv[NMAX+5],dp2[NMAX+5];
vector <pair<int,int>> vv[NMAX+5];
void dfs(int nod,int tata,int ind)
{
    ++cnt;
    ine[ind][nod]=cnt;
    lv[ind][nod]=lv[ind][tata]+1;
    for (int i=0;i<v[ind][nod].size();++i)
    {
        dfs(v[ind][nod][i],nod,ind);
    }
}
void read(int ind)
{
    for (int i=1;i<=n;++i)
    {
        cin>>t[ind][i];
        if (t[ind][i]==-1) cen[ind]=i;
        else {v[ind][t[ind][i]].push_back(i);}
    }
    cnt=0;
    dfs(cen[ind],0,ind);
    for (int i=1;i<=n;++i)
    {
        invine[ind][ine[ind][i]]=i;
    }
}
int cmp(int x,int y)
{
    return ine[1][x]<ine[1][y];
}
int lca(int x,int y,int ind)
{
    if (lv[ind][x]>lv[ind][y]) swap(x,y);
    for (int i=20;i>=0;--i) {if (lv[ind][x]+(1<<i)<=lv[ind][y]) {y=rmq[ind][i][y];}}
    if (x==y) return x;
    for (int i=20;i>=0;--i) {if (rmq[ind][i][x]!=rmq[ind][i][y]) {x=rmq[ind][i][x]; y=rmq[ind][i][y];}}
    return t[ind][x];
}
void bfs(int nod)
{
    sz[nod]=ap[nod];
    for (int i=0;i<v[1][nod].size();++i)
    {
        bfs(v[1][nod][i]);
        sz[nod]+=sz[v[1][nod][i]];
    }
}
void mfs(int nod,int tata)
{
    for (int i=0;i<v[1][nod].size();++i)
    {
        if (sz[nod]==sz[v[1][nod][i]]) {mfs(v[1][nod][i],tata); return ;}
    }
    vv[tata].push_back({nod,0});
    tt[nod]=tata;
    for (int i=0;i<v[1][nod].size();++i)
    {
        if (sz[v[1][nod][i]])
        {
            mfs(v[1][nod][i],nod);
        }
    }
}
int findfirst(int x)
{
    if (ap[x]==1) return x;
    return findfirst(vv[x][0].first);
}
int findlast(int x)
{
    if (vv[x].size()==0) return x;
    return findlast(vv[x][vv[x].size()-1].first);
}
int sum(int x,int stop)
{
    if (x==stop) return 0;
    return tv[x]+sum(tt[x],stop);
}
void lfs(int nod)
{
    if (vv[nod].size()==0)
    {
        return ;
    }
    for (int i=0;i<vv[nod].size();++i)
    {
        lfs(vv[nod][i].first);
        if (i)
        {
            int x=findlast(vv[nod][i-1].first);
            int y=findfirst(vv[nod][i].first);
            int xx=invid[x],yy=invid[y];
            vv[nod][i-1].second=ras[xx].second.first-sum(x,vv[nod][i-1].first);
            tv[vv[nod][i-1].first]=vv[nod][i-1].second;
            vv[nod][i].second=ras[xx].second.second-sum(y,vv[nod][i].first);
            tv[vv[nod][i].first]=vv[nod][i].second;
        }
    }
    if (vv[nod].size()==1)
    {
        int xx=invid[nod];
        vv[nod][0].second=ras[xx].second.second-sum(id[xx+1],vv[nod][0].first);
        tv[vv[nod][0].first]=vv[nod][0].second;
    }
}
void ylf(int nod)
{
    for (int i=0;i<vv[nod].size();++i)
    {
        dp2[vv[nod][i].first]=dp2[nod]+vv[nod][i].second;
        ylf(vv[nod][i].first);
    }
}
void solve1()
{
    for (int i=1;i<=k;++i)
    {
        ap[id[i]]=1;
    }
    bfs(cen[1]);
    mfs(cen[1],0);
    int ce=vv[0][0].first;
    lfs(ce);
    ylf(ce);
}
void solve0()
{
    int ii=0;
    for (int i=1;i<=k;++i)
    {
        if (id[i]==cen[0]) {ii=i;}
    }
    dp[ii]=0;
    for (int i=ii+1;i<=k;++i)
    {
        dp[id[i]]=dp[id[i-1]]-ras[i-1].first.first+ras[i-1].first.second;
    }
    for (int i=ii-1;i>=1;--i)
    {
        dp[id[i]]=dp[id[i+1]]-ras[i].first.second+ras[i].first.first;
    }
}
void makermq(int ind)
{
    for (int i=1;i<=n;++i)
    {
        if (t[ind][i]==-1) rmq[ind][0][i]=0;
        else rmq[ind][0][i]=t[ind][i];
    }
    for (int j=1;j<=20;++j)
    {
        for (int i=1;i<=n;++i)
        {
            rmq[ind][j][i]=rmq[ind][j-1][rmq[ind][j-1][i]];
        }
    }
}

signed main()
{
    cin>>n>>k>>q>>T;
    read(0);
    read(1);
    for (int i=1;i<=k;++i)
    {
        imp[i]=invine[0][i];
        cout<<imp[i]<<" ";
    }
        cout<<endl;
    for (int i=1;i<=k;++i)
    {
        id[i]=imp[i];
    }
    sort(id+1,id+k+1,cmp);
    for (int i=1;i<=k;++i)
    {
        invid[id[i]]=i;
    }
    for (int i=1;i<k;++i)
    {
        cout<<"? "<<id[i]<<" "<<id[i+1]<<endl;
    }
    cout<<"!"<<endl;
    for (int i=1;i<k;++i)
    {
        cin>>ras[i].first.first>>ras[i].first.second>>ras[i].second.first>>ras[i].second.second;
    }
    solve0();
    makermq(0);
    makermq(1);
    solve1();
    for (int i=1;i<=T;++i)
    {
        int x,y;
        cin>>x>>y;
        rr[1][i]=dp2[x]+dp2[y]-2*dp2[lca(x,y,1)];
        rr[0][i]=dp[x]+dp[y]-2*dp[lca(x,y,0)];
    }
    for (int i=1;i<=T;++i)
        cout<<rr[0][i]<<" "<<rr[1][i]<<'\n';
    cout.flush();
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:17:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0;i<v[ind][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void bfs(long long int)':
Main.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void mfs(long long int, long long int)':
Main.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp:66:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void lfs(long long int)':
Main.cpp:95:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i=0;i<vv[nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~
Main.cpp:102:29: warning: unused variable 'yy' [-Wunused-variable]
  102 |             int xx=invid[x],yy=invid[y];
      |                             ^~
Main.cpp: In function 'void ylf(long long int)':
Main.cpp:118:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i=0;i<vv[nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 407356 KB Output is correct
2 Correct 1147 ms 407448 KB Output is correct
3 Correct 850 ms 370376 KB Output is correct
4 Correct 847 ms 371604 KB Output is correct
5 Correct 942 ms 368640 KB Output is correct
6 Correct 1008 ms 375716 KB Output is correct
7 Correct 1092 ms 375404 KB Output is correct
8 Correct 999 ms 374368 KB Output is correct
9 Correct 822 ms 369876 KB Output is correct
10 Correct 854 ms 370168 KB Output is correct
11 Correct 802 ms 368520 KB Output is correct
12 Correct 859 ms 371192 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 408812 KB Output is correct
2 Correct 1097 ms 406252 KB Output is correct
3 Correct 892 ms 373048 KB Output is correct
4 Correct 940 ms 372836 KB Output is correct
5 Correct 947 ms 373624 KB Output is correct
6 Correct 1134 ms 376532 KB Output is correct
7 Correct 1154 ms 378296 KB Output is correct
8 Correct 1288 ms 376504 KB Output is correct
9 Correct 1243 ms 377688 KB Output is correct
10 Correct 1244 ms 377664 KB Output is correct
11 Correct 1042 ms 377400 KB Output is correct
12 Correct 1160 ms 376416 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 391856 KB Output is correct
2 Correct 725 ms 390484 KB Output is correct
3 Correct 494 ms 355032 KB Output is correct
4 Correct 514 ms 355288 KB Output is correct
5 Correct 663 ms 355060 KB Output is correct
6 Correct 608 ms 364160 KB Output is correct
7 Correct 603 ms 360920 KB Output is correct
8 Correct 628 ms 360908 KB Output is correct
9 Correct 608 ms 359760 KB Output is correct
10 Correct 597 ms 360920 KB Output is correct
11 Correct 646 ms 359380 KB Output is correct
12 Correct 686 ms 360864 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2051 ms 603408 KB Output is correct
2 Correct 2166 ms 603400 KB Output is correct
3 Correct 1376 ms 535248 KB Output is correct
4 Correct 1387 ms 534884 KB Output is correct
5 Correct 1413 ms 534872 KB Output is correct
6 Correct 1760 ms 550000 KB Output is correct
7 Correct 1734 ms 550532 KB Output is correct
8 Correct 1819 ms 549920 KB Output is correct
9 Correct 1662 ms 547560 KB Output is correct
10 Correct 1662 ms 547260 KB Output is correct
11 Correct 1620 ms 546696 KB Output is correct
12 Correct 1629 ms 546940 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2264 ms 637748 KB Output is correct
2 Correct 2304 ms 637280 KB Output is correct
3 Correct 1668 ms 563712 KB Output is correct
4 Correct 1781 ms 566504 KB Output is correct
5 Correct 1639 ms 563096 KB Output is correct
6 Correct 2308 ms 581016 KB Output is correct
7 Correct 2175 ms 577776 KB Output is correct
8 Correct 2165 ms 579688 KB Output is correct
9 Correct 2037 ms 576544 KB Output is correct
10 Correct 2045 ms 575872 KB Output is correct
11 Correct 2160 ms 575648 KB Output is correct
12 Correct 2047 ms 577596 KB Output is correct