oj.uz

Submission #1039804

# Submission time Handle Problem Language Result Execution time Memory
1039804 2024-07-31T09:29:26 Z 12345678 Inside information (BOI21_servers) C++17
0 / 100
 27 ms 9056 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=250005, kx=18, mod=400;

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], lstupd, 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 id)
{
    if (in[a[id]]<=in[b[id]]&&in[b[id]]<=out[a[id]]) return {a[id], 0};
    int tmp=a[id];
    for (int i=kx-1; i>=0; i--) if (!(in[pa[tmp][id]]<=in[b[id]]&&in[b[id]]<=out[pa[tmp][id]])) tmp=pa[tmp][id];
    if (lvl[up[a[id]]]>lvl[pa[tmp][0]]) return {-1, 0};
    return {pa[tmp][0], pw[tmp]};
}

int query(int id)
{
    auto [u, lst]=query1(id);
    if (u==-1) return 0;
    else
    {
        if (u==b[id]&&lst<=cnt[id]) return 1;
        else if (u==b[id]&&lst>cnt[id]) return 0;
        else
        {
            int vl=pw[b[id]], tmp=b[id];
            if (lvl[dn[b[id]]]>lvl[u]||pw[b[id]]>cnt[id]) 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;
            }
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    //freopen("server.in","r",stdin);
    //freopen("server.out","w",stdout);
    cin>>n>>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)
            {
                lstupd=cnt[i];
                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];
                lstupd=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=lstupd+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:44:17: warning: unused variable 'vl' [-Wunused-variable]
   44 |             int vl=pw[b[id]], tmp=b[id];
      |                 ^~

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 9056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 9056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 9056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 9056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -