oj.uz

Submission #1040407

# Submission time Handle Problem Language Result Execution time Memory
1040407 2024-08-01T03:34:36 Z 12345678 Inside information (BOI21_servers) C++17
100 / 100
 2076 ms 71000 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=250005, kx=18, mod=200;
 
int n, k, a[nx], b[nx], idx[nx], cnt[nx], lvl[nx], pa[nx][kx], up[nx], dn[nx], pw[nx], t, in[nx], out[nx], lst, dp[nx], l[nx], r[nx], pts[nx];
char opr[nx];
vector<pair<int, int>> d[nx];
 
void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    in[u]=++t;
    up[u]=p;
    if (pw[u]<pw[p]) up[u]=up[p];
    dn[u]=p;
    if (pw[u]>pw[p]) dn[u]=dn[p];
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) pw[v]=w, dfs(v, u);
    out[u]=t;
}
 
pair<int, int> query1(int idx)
{
    if (in[a[idx]]<=in[b[idx]]&&in[b[idx]]<=out[a[idx]]) return {a[idx], 0};
    int tmp=a[idx];
    for (int i=kx-1; i>=0; i--) if (!(in[pa[tmp][i]]<=in[b[idx]]&&in[b[idx]]<=out[pa[tmp][i]])) tmp=pa[tmp][i];
    if (lvl[up[a[idx]]]>lvl[pa[tmp][0]]) return {-1, 0};
    return {pa[tmp][0], pw[tmp]};
}
 
int query(int i)
{
    auto [u, lst]=query1(i);
    if (u==-1) return 0;
    else
    {
        if (u==b[i]&&lst<=cnt[i]) return 1;
        else if (u==b[i]&&lst>cnt[i]) return 0;
        else
        {
            int vl=pw[b[i]], tmp=b[i];
            if (lvl[dn[b[i]]]>lvl[u]||pw[b[i]]>cnt[i]) return 0;
            else
            {
                for (int j=kx-1; j>=0; j--) if (lvl[pa[tmp][j]]>lvl[u]) tmp=pa[tmp][j];
                if (lst<pw[tmp]) return 1;
                else return 0;
            }
        }
    }
}
 
void solve()
{
    int vs[n+1][n+1], xx, yy;
    char cc;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) vs[i][j]=0;
    cin>>k;
    for (int i=1; i<=n; i++) vs[i][i]=i;
    for (int i=1; i<n+k; i++)
    {
        cin>>cc;
        if (cc=='S')
        {
            cin>>xx>>yy;
            for (int j=1; j<=n; j++) vs[xx][j]=vs[yy][j]=(vs[xx][j]||vs[yy][j]);
        }
        if (cc=='Q') cin>>xx>>yy, cout<<(vs[xx][yy]?"yes\n":"no\n");
        if (cc=='C')
        {
            cin>>xx;
            int cnt=0;
            for (int j=1; j<=n; j++) if (vs[j][xx]) cnt++;
            cout<<cnt<<'\n';
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    if (n<=4000) return solve(), 0;
    cin>>k;
    for (int i=1; i<=n; i++) pts[i]=i, dp[i]=1;
    for (int i=1; i<n+k; i++)
    {
        cin>>opr[i];
        cnt[i]=cnt[i-1];
        if (opr[i]=='S') cin>>a[i]>>b[i], idx[++cnt[i]]=i, d[a[i]].push_back({b[i], cnt[i]}), d[b[i]].push_back({a[i], cnt[i]}), l[cnt[i]+n]=pts[a[i]], r[cnt[i]+n]=pts[b[i]], pts[a[i]]=pts[b[i]]=cnt[i]+n;
        if (opr[i]=='Q') cin>>b[i]>>a[i];
        if (opr[i]=='C') cin>>a[i];
    }
    dfs(1, 1);
    for (int i=1; i<n+k; i++)
    {
        if (opr[i]=='S')
        {
            if ((cnt[i]%mod)==0)
            {
                for (int j=1; j<=n+cnt[j]; j++) dp[j]=1;
                for (int j=n+cnt[i]; j>=n+1; j--) dp[l[j]]+=dp[j], dp[r[j]]+=dp[j];
                lst=cnt[i];
            }
        }
        if (opr[i]=='Q') cout<<(query(i)?"yes\n":"no\n");
        if (opr[i]=='C') 
        {
            int tmp=dp[a[i]];
            for (int j=lst+1; j<=cnt[i]; j++) 
            {
                int f=1;
                b[i]=a[idx[j]];
                if (!query(i)) f=0;
                b[i]=b[idx[j]];
                if (!query(i)) f=0;
                tmp+=f;
            }
            cout<<tmp<<'\n';
        }
    }
}

Compilation message

servers.cpp: In function 'int query(int)':
servers.cpp:47:17: warning: unused variable 'vl' [-Wunused-variable]
   47 |             int vl=pw[b[i]], tmp=b[i];
      |                 ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7004 KB Output is correct
2 Correct 63 ms 69712 KB Output is correct
3 Correct 54 ms 69668 KB Output is correct
4 Correct 63 ms 69712 KB Output is correct
5 Correct 61 ms 69712 KB Output is correct
6 Correct 60 ms 69716 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7004 KB Output is correct
2 Correct 63 ms 69712 KB Output is correct
3 Correct 54 ms 69668 KB Output is correct
4 Correct 63 ms 69712 KB Output is correct
5 Correct 61 ms 69712 KB Output is correct
6 Correct 60 ms 69716 KB Output is correct
7 Correct 10 ms 7004 KB Output is correct
8 Correct 1152 ms 69664 KB Output is correct
9 Correct 793 ms 70736 KB Output is correct
10 Correct 1202 ms 70740 KB Output is correct
11 Correct 1189 ms 70588 KB Output is correct
12 Correct 762 ms 70992 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7004 KB Output is correct
2 Correct 184 ms 33476 KB Output is correct
3 Correct 190 ms 33480 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7004 KB Output is correct
2 Correct 184 ms 33476 KB Output is correct
3 Correct 190 ms 33480 KB Output is correct
4 Correct 10 ms 7004 KB Output is correct
5 Correct 613 ms 33404 KB Output is correct
6 Correct 753 ms 33732 KB Output is correct
7 Correct 1553 ms 33476 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7000 KB Output is correct
2 Correct 198 ms 41812 KB Output is correct
3 Correct 171 ms 41812 KB Output is correct
4 Correct 180 ms 41816 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7000 KB Output is correct
2 Correct 198 ms 41812 KB Output is correct
3 Correct 171 ms 41812 KB Output is correct
4 Correct 180 ms 41816 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 1168 ms 41812 KB Output is correct
7 Correct 647 ms 41844 KB Output is correct
8 Correct 2058 ms 41812 KB Output is correct
9 Correct 2076 ms 41808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 131 ms 33464 KB Output is correct
3 Correct 178 ms 33820 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 131 ms 33464 KB Output is correct
3 Correct 178 ms 33820 KB Output is correct
4 Correct 11 ms 7004 KB Output is correct
5 Correct 1566 ms 33392 KB Output is correct
6 Correct 882 ms 33840 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7000 KB Output is correct
2 Correct 187 ms 41808 KB Output is correct
3 Correct 191 ms 41808 KB Output is correct
4 Correct 177 ms 41980 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 132 ms 33540 KB Output is correct
7 Correct 175 ms 33876 KB Output is correct
8 Correct 189 ms 34384 KB Output is correct
9 Correct 189 ms 34380 KB Output is correct
10 Correct 181 ms 38736 KB Output is correct
11 Correct 177 ms 38224 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7000 KB Output is correct
2 Correct 187 ms 41808 KB Output is correct
3 Correct 191 ms 41808 KB Output is correct
4 Correct 177 ms 41980 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 132 ms 33540 KB Output is correct
7 Correct 175 ms 33876 KB Output is correct
8 Correct 189 ms 34384 KB Output is correct
9 Correct 189 ms 34380 KB Output is correct
10 Correct 181 ms 38736 KB Output is correct
11 Correct 177 ms 38224 KB Output is correct
12 Correct 11 ms 7004 KB Output is correct
13 Correct 1178 ms 41808 KB Output is correct
14 Correct 674 ms 41808 KB Output is correct
15 Correct 2064 ms 41580 KB Output is correct
16 Correct 2076 ms 41812 KB Output is correct
17 Correct 11 ms 7000 KB Output is correct
18 Correct 1538 ms 33360 KB Output is correct
19 Correct 840 ms 33872 KB Output is correct
20 Correct 1464 ms 34292 KB Output is correct
21 Correct 906 ms 34196 KB Output is correct
22 Correct 1738 ms 37884 KB Output is correct
23 Correct 1534 ms 37360 KB Output is correct
24 Correct 423 ms 37204 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 61 ms 69764 KB Output is correct
3 Correct 54 ms 69640 KB Output is correct
4 Correct 60 ms 69772 KB Output is correct
5 Correct 61 ms 69712 KB Output is correct
6 Correct 59 ms 69716 KB Output is correct
7 Correct 11 ms 7004 KB Output is correct
8 Correct 194 ms 33480 KB Output is correct
9 Correct 183 ms 33476 KB Output is correct
10 Correct 10 ms 7000 KB Output is correct
11 Correct 182 ms 41940 KB Output is correct
12 Correct 174 ms 41812 KB Output is correct
13 Correct 167 ms 41808 KB Output is correct
14 Correct 10 ms 7004 KB Output is correct
15 Correct 129 ms 33480 KB Output is correct
16 Correct 179 ms 33872 KB Output is correct
17 Correct 175 ms 34388 KB Output is correct
18 Correct 189 ms 34388 KB Output is correct
19 Correct 169 ms 38668 KB Output is correct
20 Correct 190 ms 38064 KB Output is correct
21 Correct 170 ms 33448 KB Output is correct
22 Correct 182 ms 33464 KB Output is correct
23 Correct 159 ms 33876 KB Output is correct
24 Correct 173 ms 33768 KB Output is correct
25 Correct 205 ms 35532 KB Output is correct
26 Correct 165 ms 33364 KB Output is correct
27 Correct 162 ms 33364 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 61 ms 69764 KB Output is correct
3 Correct 54 ms 69640 KB Output is correct
4 Correct 60 ms 69772 KB Output is correct
5 Correct 61 ms 69712 KB Output is correct
6 Correct 59 ms 69716 KB Output is correct
7 Correct 11 ms 7004 KB Output is correct
8 Correct 194 ms 33480 KB Output is correct
9 Correct 183 ms 33476 KB Output is correct
10 Correct 10 ms 7000 KB Output is correct
11 Correct 182 ms 41940 KB Output is correct
12 Correct 174 ms 41812 KB Output is correct
13 Correct 167 ms 41808 KB Output is correct
14 Correct 10 ms 7004 KB Output is correct
15 Correct 129 ms 33480 KB Output is correct
16 Correct 179 ms 33872 KB Output is correct
17 Correct 175 ms 34388 KB Output is correct
18 Correct 189 ms 34388 KB Output is correct
19 Correct 169 ms 38668 KB Output is correct
20 Correct 190 ms 38064 KB Output is correct
21 Correct 170 ms 33448 KB Output is correct
22 Correct 182 ms 33464 KB Output is correct
23 Correct 159 ms 33876 KB Output is correct
24 Correct 173 ms 33768 KB Output is correct
25 Correct 205 ms 35532 KB Output is correct
26 Correct 165 ms 33364 KB Output is correct
27 Correct 162 ms 33364 KB Output is correct
28 Correct 11 ms 7004 KB Output is correct
29 Correct 1172 ms 69712 KB Output is correct
30 Correct 794 ms 70868 KB Output is correct
31 Correct 1154 ms 70644 KB Output is correct
32 Correct 1176 ms 70736 KB Output is correct
33 Correct 764 ms 71000 KB Output is correct
34 Correct 11 ms 8024 KB Output is correct
35 Correct 569 ms 36240 KB Output is correct
36 Correct 755 ms 35360 KB Output is correct
37 Correct 1560 ms 35528 KB Output is correct
38 Correct 17 ms 8016 KB Output is correct
39 Correct 1192 ms 44704 KB Output is correct
40 Correct 659 ms 44884 KB Output is correct
41 Correct 2073 ms 44372 KB Output is correct
42 Correct 2044 ms 44460 KB Output is correct
43 Correct 11 ms 8028 KB Output is correct
44 Correct 1546 ms 36432 KB Output is correct
45 Correct 856 ms 36692 KB Output is correct
46 Correct 1538 ms 37144 KB Output is correct
47 Correct 881 ms 37232 KB Output is correct
48 Correct 1786 ms 40556 KB Output is correct
49 Correct 1475 ms 40360 KB Output is correct
50 Correct 462 ms 40528 KB Output is correct
51 Correct 1159 ms 36688 KB Output is correct
52 Correct 1744 ms 36368 KB Output is correct
53 Correct 1542 ms 36000 KB Output is correct
54 Correct 797 ms 36604 KB Output is correct
55 Correct 1554 ms 36268 KB Output is correct
56 Correct 768 ms 36948 KB Output is correct
57 Correct 909 ms 38092 KB Output is correct
58 Correct 1299 ms 35920 KB Output is correct
59 Correct 311 ms 36556 KB Output is correct