oj.uz

Submission #530481

# Submission time Handle Problem Language Result Execution time Memory
530481 2022-02-25T13:40:34 Z azberjibiou Inside information (BOI21_servers) C++17
100 / 100
 544 ms 65232 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=120005;
const int mxM=1010;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1e15;
const ll P1=1000000007;
const ll P2=1000000009;
typedef struct query{
    char typ;
    int s, e;
}edge;
int N, K;
vector <pii> vadj[mxN], eadj[mxN];
vector <int> echild[mxN];
query Q[2*mxN];
int vpar[mxN], vsps[20][mxN], vdep[mxN];
int edep[mxN], cursum[mxN], esps[20][mxN];
int g[mxN];
int sub[mxN];
int in[mxN], out[mxN], eidx;
int ntime;
void dfsv0(int now, int pre)
{
    for(pii ele : vadj[now])    if(ele.fir!=pre)
    {
        vdep[ele.fir]=vdep[now]+1;
        vpar[ele.fir]=ele.sec;
        vsps[0][ele.fir]=now;
        dfsv0(ele.fir, now);
    }
}
void dfse0(int now, int pre)
{
    sub[now]=1;
    for(pii ele : eadj[now]) if(ele.fir!=pre)
    {
        echild[now].push_back(ele.fir);
        esps[0][ele.fir]=now;
        edep[ele.fir]=edep[now]+1;
        cursum[ele.fir]+=cursum[now]+ele.sec;
        dfse0(ele.fir, now);
        sub[now]+=sub[ele.fir];
    }
    for(int i=1;i<echild[now].size();i++)
    {
        if(sub[echild[now][0]]<sub[echild[now][i]]) swap(echild[now][0], echild[now][i]);
    }
}
void dfse1(int now)
{
    in[now]=++eidx;
    if(echild[now].empty()) return;
    g[echild[now][0]]=g[now];
    for(int i=1;i<echild[now].size();i++)  g[echild[now][i]]=echild[now][i];
    for(int ele : echild[now])  dfse1(ele);
    out[now]=eidx;
}
void solvN1()
{
    for(int i=0;i<N+K;i++)
    {
        if(Q[i].typ=='C')   cout << 1 << '\n';
        if(Q[i].typ=='Q')   cout << "yes" << '\n';
    }
}
int solv_lca(int a, int b, int sps[][mxN], int *dep)
{
    if(dep[a]<dep[b])   swap(a, b);
    for(int i=19;i>=0;i--)
    {
        if(dep[a]>=dep[b]+(1<<i))   a=sps[i][a];
    }
    if(a==b)    return a;
    for(int i=19;i>=0;i--)  if(sps[i][a]!=sps[i][b])    a=sps[i][a], b=sps[i][b];
    return sps[0][a];
}
int vdown_edge(int s, int e)
{
    for(int i=19;i>=0;i--)  if(vdep[s]>vdep[e]+(1<<i))  s=vsps[i][s];
    return s;
}
ll seg[4*mxN], lazy[4*mxN];
void propagate(int idx, int s, int e)
{
    int mid=(s+e)/2;
    seg[2*idx]+=(mid-s+1)*lazy[idx];
    seg[2*idx+1]+=(e-mid)*lazy[idx];
    lazy[2*idx]+=lazy[idx];
    lazy[2*idx+1]+=lazy[idx];
    lazy[idx]=0;
}
void seg_upd(int idx, int s1, int e1, int s2, int e2)
{
    if(s1>e2 || s2>e1)  return;
    if(s2<=s1 && e1<=e2)
    {
        seg[idx]+=e1-s1+1;
        lazy[idx]++;
        return;
    }
    propagate(idx, s1, e1);
    int mid=(s1+e1)/2;
    seg_upd(2*idx, s1, mid, s2, e2);
    seg_upd(2*idx+1, mid+1, e1, s2, e2);
    seg[idx]=seg[2*idx]+seg[2*idx+1];
}
int seg_solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s2>e1 || s1>e2)  return 0;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    propagate(idx, s1, e1);
    int mid=(s1+e1)/2;
    return seg_solv(2*idx, s1, mid, s2, e2)+seg_solv(2*idx+1, mid+1, e1, s2, e2);
}
void hld_upd(int s, int e)
{
    while(edep[g[s]]>edep[e])
    {
        seg_upd(1, 1, N-1, in[g[s]], in[s]);
        s=esps[0][g[s]];
    }
    seg_upd(1, 1, N-1, in[e], in[s]);
}
int hld_solv(int s, int e)
{
    int ret=0;
    while(edep[g[s]]>edep[e])
    {
        ret+=seg_solv(1, 1, N-1, in[g[s]], in[s]);
        s=esps[0][g[s]];
    }
    ret+=seg_solv(1, 1, N-1, in[e], in[s]);
    return ret;
}
int solvC(int now)
{
    int enow=vadj[now][0].sec;
    int npar=enow;
    for(int i=19;i>=0;i--)
    {
        if(esps[i][npar]!=0 && cursum[esps[i][npar]]==cursum[enow])    npar=esps[i][npar];
    }
    return hld_solv(enow, npar);
}
bool esolvQ(int now, int data)
{
    //printf("now=%d, data=%d\n", now, data);
    //printf("ntime=%d\n", ntime);
    if(now==data)   return (now<=ntime);
    int elca=solv_lca(now, data, esps, edep);
    return (cursum[data]==cursum[elca] && cursum[elca]-cursum[now]==edep[elca]-edep[now] && now<=ntime);
}
bool solvQ(int now, int data)
{
    if(now==data)   return true;
    int vlca=solv_lca(now, data, vsps, vdep);
    if(vlca==now)
    {
        return esolvQ(vpar[vdown_edge(data, now)], vpar[data]);
    }
    else if(vlca==data)
    {
        return esolvQ(vpar[now], vpar[vdown_edge(now, data)]);
    }
    else
    {
        return esolvQ(vpar[now], vpar[data]);
    }
}
void eupd(int now)
{
    int npar=now;
    for(int i=19;i>=0;i--)
    {
        if(esps[i][npar]!=0 && cursum[esps[i][npar]]-cursum[npar]==edep[esps[i][npar]]-edep[npar])  npar=esps[i][npar];
    }
    hld_upd(now, npar);
}
int main()
{
    gibon
    cin >> N >> K;
    int idx=1;
    for(int i=0;i<N+K-1;i++)
    {
        cin >> Q[i].typ;
        if(Q[i].typ=='C')   cin >> Q[i].s;
        else    cin >> Q[i].s >> Q[i].e;
        if(Q[i].typ=='S')
        {
            vadj[Q[i].s].emplace_back(Q[i].e, idx);
            vadj[Q[i].e].emplace_back(Q[i].s, idx);
            idx++;
        }
    }
    if(N==1)
    {
        solvN1();
        return 0;
    }
    for(int i=1;i<=N;i++)
    {
        if(vadj[i].size())
            sort(vadj[i].begin(), vadj[i].end(), [](pii a, pii b){return a.sec<b.sec;});
        for(int j=0;j+1<vadj[i].size();j++)
        {
            eadj[vadj[i][j].sec].emplace_back(vadj[i][j+1].sec, 1);
            eadj[vadj[i][j+1].sec].emplace_back(vadj[i][j].sec, 0);
        }
    }
    dfsv0(1, -1);
    for(int i=1;i<20;i++)   for(int j=1;j<=N;j++)   vsps[i][j]=vsps[i-1][vsps[i-1][j]];
    g[1]=1;
    dfse0(1, -1);
    dfse1(1);
    for(int i=1;i<20;i++)   for(int j=1;j<=N;j++)   esps[i][j]=esps[i-1][esps[i-1][j]];
    /*for(int i=1;i<N;i++)
    {
        printf("i=%d: ", i);
        for(auto ele : eadj[i]) printf("(%d, %d) ", ele.fir, ele.sec);
        printf("\n");
    }
    for(int i=1;i<N;i++)    printf("in[%d]=%d\n", i, in[i]);
    for(int i=1;i<N;i++)    printf("g[%d]=%d\n", i, g[i]);*/
    for(int i=0;i<N+K-1;i++)
    {
        if(Q[i].typ=='S')
        {
            ntime++;
            eupd(ntime);
        }
        if(Q[i].typ=='C')
        {
            cout << solvC(Q[i].s)+1 << '\n';
        }
        if(Q[i].typ=='Q')
        {
            cout << (solvQ(Q[i].s, Q[i].e) ? "yes" : "no") << '\n';
        }
    }
}

Compilation message

servers.cpp: In function 'void dfse0(int, int)':
servers.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=1;i<echild[now].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void dfse1(int)':
servers.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=1;i<echild[now].size();i++)  g[echild[now][i]]=echild[now][i];
      |                 ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:217:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for(int j=0;j+1<vadj[i].size();j++)
      |                     ~~~^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11584 KB Output is correct
2 Correct 60 ms 13380 KB Output is correct
3 Correct 66 ms 13596 KB Output is correct
4 Correct 79 ms 13580 KB Output is correct
5 Correct 76 ms 13604 KB Output is correct
6 Correct 53 ms 13808 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11584 KB Output is correct
2 Correct 60 ms 13380 KB Output is correct
3 Correct 66 ms 13596 KB Output is correct
4 Correct 79 ms 13580 KB Output is correct
5 Correct 76 ms 13604 KB Output is correct
6 Correct 53 ms 13808 KB Output is correct
7 Correct 37 ms 11608 KB Output is correct
8 Correct 81 ms 13124 KB Output is correct
9 Correct 85 ms 13336 KB Output is correct
10 Correct 84 ms 13252 KB Output is correct
11 Correct 74 ms 13364 KB Output is correct
12 Correct 54 ms 13696 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11612 KB Output is correct
2 Correct 273 ms 64944 KB Output is correct
3 Correct 261 ms 64904 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11612 KB Output is correct
2 Correct 273 ms 64944 KB Output is correct
3 Correct 261 ms 64904 KB Output is correct
4 Correct 37 ms 11588 KB Output is correct
5 Correct 313 ms 64860 KB Output is correct
6 Correct 151 ms 64004 KB Output is correct
7 Correct 172 ms 64200 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11640 KB Output is correct
2 Correct 286 ms 62436 KB Output is correct
3 Correct 338 ms 59376 KB Output is correct
4 Correct 265 ms 64440 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11640 KB Output is correct
2 Correct 286 ms 62436 KB Output is correct
3 Correct 338 ms 59376 KB Output is correct
4 Correct 265 ms 64440 KB Output is correct
5 Correct 52 ms 11596 KB Output is correct
6 Correct 407 ms 60780 KB Output is correct
7 Correct 431 ms 64120 KB Output is correct
8 Correct 489 ms 61988 KB Output is correct
9 Correct 467 ms 59004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11696 KB Output is correct
2 Correct 277 ms 53616 KB Output is correct
3 Correct 293 ms 53344 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11696 KB Output is correct
2 Correct 277 ms 53616 KB Output is correct
3 Correct 293 ms 53344 KB Output is correct
4 Correct 37 ms 11560 KB Output is correct
5 Correct 376 ms 53320 KB Output is correct
6 Correct 343 ms 52952 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11588 KB Output is correct
2 Correct 290 ms 62372 KB Output is correct
3 Correct 253 ms 59332 KB Output is correct
4 Correct 315 ms 64512 KB Output is correct
5 Correct 46 ms 11588 KB Output is correct
6 Correct 276 ms 53588 KB Output is correct
7 Correct 261 ms 53512 KB Output is correct
8 Correct 497 ms 54084 KB Output is correct
9 Correct 315 ms 54136 KB Output is correct
10 Correct 263 ms 57224 KB Output is correct
11 Correct 368 ms 57076 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11588 KB Output is correct
2 Correct 290 ms 62372 KB Output is correct
3 Correct 253 ms 59332 KB Output is correct
4 Correct 315 ms 64512 KB Output is correct
5 Correct 46 ms 11588 KB Output is correct
6 Correct 276 ms 53588 KB Output is correct
7 Correct 261 ms 53512 KB Output is correct
8 Correct 497 ms 54084 KB Output is correct
9 Correct 315 ms 54136 KB Output is correct
10 Correct 263 ms 57224 KB Output is correct
11 Correct 368 ms 57076 KB Output is correct
12 Correct 39 ms 11592 KB Output is correct
13 Correct 403 ms 60792 KB Output is correct
14 Correct 377 ms 64152 KB Output is correct
15 Correct 501 ms 62028 KB Output is correct
16 Correct 438 ms 58968 KB Output is correct
17 Correct 38 ms 11584 KB Output is correct
18 Correct 358 ms 53316 KB Output is correct
19 Correct 419 ms 52960 KB Output is correct
20 Correct 458 ms 53736 KB Output is correct
21 Correct 544 ms 53752 KB Output is correct
22 Correct 420 ms 56668 KB Output is correct
23 Correct 342 ms 55996 KB Output is correct
24 Correct 267 ms 55940 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11628 KB Output is correct
2 Correct 63 ms 13468 KB Output is correct
3 Correct 57 ms 13560 KB Output is correct
4 Correct 84 ms 13612 KB Output is correct
5 Correct 78 ms 13596 KB Output is correct
6 Correct 55 ms 13928 KB Output is correct
7 Correct 36 ms 11600 KB Output is correct
8 Correct 253 ms 64876 KB Output is correct
9 Correct 263 ms 64968 KB Output is correct
10 Correct 36 ms 11588 KB Output is correct
11 Correct 336 ms 62552 KB Output is correct
12 Correct 253 ms 59332 KB Output is correct
13 Correct 287 ms 64372 KB Output is correct
14 Correct 37 ms 11692 KB Output is correct
15 Correct 286 ms 53648 KB Output is correct
16 Correct 317 ms 53356 KB Output is correct
17 Correct 374 ms 54140 KB Output is correct
18 Correct 311 ms 54196 KB Output is correct
19 Correct 257 ms 57124 KB Output is correct
20 Correct 351 ms 56992 KB Output is correct
21 Correct 300 ms 59864 KB Output is correct
22 Correct 301 ms 59812 KB Output is correct
23 Correct 369 ms 55060 KB Output is correct
24 Correct 368 ms 55236 KB Output is correct
25 Correct 315 ms 58488 KB Output is correct
26 Correct 202 ms 53316 KB Output is correct
27 Correct 195 ms 53420 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11628 KB Output is correct
2 Correct 63 ms 13468 KB Output is correct
3 Correct 57 ms 13560 KB Output is correct
4 Correct 84 ms 13612 KB Output is correct
5 Correct 78 ms 13596 KB Output is correct
6 Correct 55 ms 13928 KB Output is correct
7 Correct 36 ms 11600 KB Output is correct
8 Correct 253 ms 64876 KB Output is correct
9 Correct 263 ms 64968 KB Output is correct
10 Correct 36 ms 11588 KB Output is correct
11 Correct 336 ms 62552 KB Output is correct
12 Correct 253 ms 59332 KB Output is correct
13 Correct 287 ms 64372 KB Output is correct
14 Correct 37 ms 11692 KB Output is correct
15 Correct 286 ms 53648 KB Output is correct
16 Correct 317 ms 53356 KB Output is correct
17 Correct 374 ms 54140 KB Output is correct
18 Correct 311 ms 54196 KB Output is correct
19 Correct 257 ms 57124 KB Output is correct
20 Correct 351 ms 56992 KB Output is correct
21 Correct 300 ms 59864 KB Output is correct
22 Correct 301 ms 59812 KB Output is correct
23 Correct 369 ms 55060 KB Output is correct
24 Correct 368 ms 55236 KB Output is correct
25 Correct 315 ms 58488 KB Output is correct
26 Correct 202 ms 53316 KB Output is correct
27 Correct 195 ms 53420 KB Output is correct
28 Correct 40 ms 11612 KB Output is correct
29 Correct 68 ms 13040 KB Output is correct
30 Correct 67 ms 13356 KB Output is correct
31 Correct 81 ms 13316 KB Output is correct
32 Correct 79 ms 13388 KB Output is correct
33 Correct 59 ms 13684 KB Output is correct
34 Correct 36 ms 11696 KB Output is correct
35 Correct 254 ms 64868 KB Output is correct
36 Correct 156 ms 64044 KB Output is correct
37 Correct 162 ms 64216 KB Output is correct
38 Correct 39 ms 11572 KB Output is correct
39 Correct 406 ms 60764 KB Output is correct
40 Correct 395 ms 64136 KB Output is correct
41 Correct 444 ms 61892 KB Output is correct
42 Correct 470 ms 59116 KB Output is correct
43 Correct 38 ms 11596 KB Output is correct
44 Correct 370 ms 53240 KB Output is correct
45 Correct 414 ms 53016 KB Output is correct
46 Correct 442 ms 53692 KB Output is correct
47 Correct 443 ms 53824 KB Output is correct
48 Correct 399 ms 56772 KB Output is correct
49 Correct 351 ms 55876 KB Output is correct
50 Correct 239 ms 55956 KB Output is correct
51 Correct 202 ms 59620 KB Output is correct
52 Correct 184 ms 65040 KB Output is correct
53 Correct 210 ms 64564 KB Output is correct
54 Correct 162 ms 65232 KB Output is correct
55 Correct 182 ms 64356 KB Output is correct
56 Correct 338 ms 54860 KB Output is correct
57 Correct 261 ms 59744 KB Output is correct
58 Correct 371 ms 52420 KB Output is correct
59 Correct 265 ms 53380 KB Output is correct