oj.uz

Submission #577159

# Submission time Handle Problem Language Result Execution time Memory
577159 2022-06-14T08:06:26 Z Valters07 Inside information (BOI21_servers) C++14
53 / 100
 196 ms 32716 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
#define r0 return 0;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 120005;
const int LOG = log2(N)+2;
vector<pair<int,int> > g[N];
int par[N][LOG], tin[N], tout[N], tt;
int down[N], up[N], dep[N];
int topar[N];
void dfs(int u, int p)
{
    tin[u]=++tt;
    par[u][0]=p;
    for(int i = 1;i<LOG;i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:g[u])
    {
        if(v.fi!=p)
        {
            topar[v.fi]=v.se;
            down[v.fi]=(v.se>topar[u]||u==1?down[u]+1:1);
            up[v.fi]=(v.se<topar[u]||u==1?up[u]+1:1);
            dep[v.fi]=dep[u]+1;
            dfs(v.fi,u);
        }
    }
    tout[u]=tt;
}
bool is_anc(int u, int v)
{
    return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
int main()
{
    fio
    //ifstream cin("in.in");
    int n, q;
    cin >> n >> q;
    vector<pair<pair<int,int>,int> > qu;
    for(int i = 1;i<n+q;i++)
    {
        char c;
        cin >> c;
        if(c=='C')
            return 0;
        int u, v;
        cin >> u >> v;
        if(c=='Q')
            qu.pb({{u,v},i});
        else
            g[u].pb({v,i}),
            g[v].pb({u,i});
    }
    dfs(1,1);
    for(auto i:qu)
    {
        int u = i.fi.fi, v = i.fi.se, t = i.se;
        swap(u,v);
        if(u==v)
            cout << "yes";
        else if(is_anc(u,v))
            cout << ((dep[v]-dep[u])<=down[v]&&topar[v]<t?"yes":"no");
        else if(is_anc(v,u))
        {
            int u1 = u;
            for(int i = LOG-1;i>=0;i--)
                if(!is_anc(par[u1][i],v))
                    u1=par[u1][i];
            cout << ((dep[u]-dep[v])<=up[u]&&topar[u1]<t?"yes":"no");
        }
        else
        {
            int u1 = u, v1 = v;
            for(int i = LOG-1;i>=0;i--)
            {
                if(!is_anc(par[u1][i],v))
                    u1=par[u1][i];
                if(!is_anc(par[v1][i],u))
                    v1=par[v1][i];
            }
            int lca = par[u1][0];
            cout << (dep[u]-dep[lca]<=up[u]&&dep[v]-dep[lca]<=down[v]&&
                     topar[u1]<topar[v1]&&topar[v]<t?"yes":"no");
        }
        cout << "\n";
    }
    //cin.close();
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5948 KB Output is correct
2 Correct 51 ms 6756 KB Output is correct
3 Correct 46 ms 6964 KB Output is correct
4 Correct 49 ms 6860 KB Output is correct
5 Correct 44 ms 7252 KB Output is correct
6 Correct 46 ms 6868 KB Output is correct

Subtask #2
0.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5948 KB Output is correct
2 Correct 51 ms 6756 KB Output is correct
3 Correct 46 ms 6964 KB Output is correct
4 Correct 49 ms 6860 KB Output is correct
5 Correct 44 ms 7252 KB Output is correct
6 Correct 46 ms 6868 KB Output is correct
7 Partially correct 2 ms 3284 KB Output is incorrect
8 Partially correct 2 ms 3156 KB Output is incorrect
9 Partially correct 3 ms 3284 KB Output is incorrect
10 Partially correct 2 ms 3156 KB Output is incorrect
11 Partially correct 2 ms 3152 KB Output is incorrect
12 Partially correct 2 ms 3156 KB Output is incorrect

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5952 KB Output is correct
2 Correct 128 ms 23680 KB Output is correct
3 Correct 149 ms 23740 KB Output is correct

Subtask #4
0.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5952 KB Output is correct
2 Correct 128 ms 23680 KB Output is correct
3 Correct 149 ms 23740 KB Output is correct
4 Partially correct 3 ms 3284 KB Output is incorrect
5 Partially correct 2 ms 3156 KB Output is incorrect
6 Partially correct 2 ms 3156 KB Output is incorrect
7 Partially correct 2 ms 3156 KB Output is incorrect

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5952 KB Output is correct
2 Correct 137 ms 32684 KB Output is correct
3 Correct 130 ms 32644 KB Output is correct
4 Correct 113 ms 32636 KB Output is correct

Subtask #6
0.5 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5952 KB Output is correct
2 Correct 137 ms 32684 KB Output is correct
3 Correct 130 ms 32644 KB Output is correct
4 Correct 113 ms 32636 KB Output is correct
5 Partially correct 2 ms 3284 KB Output is incorrect
6 Partially correct 2 ms 3156 KB Output is incorrect
7 Partially correct 2 ms 3156 KB Output is incorrect
8 Partially correct 2 ms 3156 KB Output is incorrect
9 Partially correct 2 ms 3156 KB Output is incorrect

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5900 KB Output is correct
2 Correct 127 ms 24176 KB Output is correct
3 Correct 125 ms 24676 KB Output is correct

Subtask #8
0.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5900 KB Output is correct
2 Correct 127 ms 24176 KB Output is correct
3 Correct 125 ms 24676 KB Output is correct
4 Partially correct 2 ms 3284 KB Output is incorrect
5 Partially correct 2 ms 3164 KB Output is incorrect
6 Partially correct 23 ms 6784 KB Output is incorrect

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5860 KB Output is correct
2 Correct 125 ms 32636 KB Output is correct
3 Correct 176 ms 32696 KB Output is correct
4 Correct 116 ms 32608 KB Output is correct
5 Correct 42 ms 5948 KB Output is correct
6 Correct 110 ms 24156 KB Output is correct
7 Correct 139 ms 24648 KB Output is correct
8 Correct 186 ms 25092 KB Output is correct
9 Correct 141 ms 25060 KB Output is correct
10 Correct 157 ms 29524 KB Output is correct
11 Correct 181 ms 28836 KB Output is correct

Subtask #10
0.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5860 KB Output is correct
2 Correct 125 ms 32636 KB Output is correct
3 Correct 176 ms 32696 KB Output is correct
4 Correct 116 ms 32608 KB Output is correct
5 Correct 42 ms 5948 KB Output is correct
6 Correct 110 ms 24156 KB Output is correct
7 Correct 139 ms 24648 KB Output is correct
8 Correct 186 ms 25092 KB Output is correct
9 Correct 141 ms 25060 KB Output is correct
10 Correct 157 ms 29524 KB Output is correct
11 Correct 181 ms 28836 KB Output is correct
12 Partially correct 2 ms 3284 KB Output is incorrect
13 Partially correct 2 ms 3156 KB Output is incorrect
14 Partially correct 2 ms 3164 KB Output is incorrect
15 Partially correct 2 ms 3156 KB Output is incorrect
16 Partially correct 2 ms 3156 KB Output is incorrect
17 Partially correct 3 ms 3284 KB Output is incorrect
18 Partially correct 2 ms 3160 KB Output is incorrect
19 Partially correct 26 ms 6736 KB Output is incorrect
20 Partially correct 2 ms 3156 KB Output is incorrect
21 Partially correct 2 ms 3156 KB Output is incorrect
22 Partially correct 2 ms 3156 KB Output is incorrect
23 Partially correct 25 ms 7232 KB Output is incorrect
24 Partially correct 39 ms 8260 KB Output is incorrect

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5976 KB Output is correct
2 Correct 48 ms 6792 KB Output is correct
3 Correct 49 ms 6908 KB Output is correct
4 Correct 48 ms 6904 KB Output is correct
5 Correct 42 ms 7244 KB Output is correct
6 Correct 46 ms 6884 KB Output is correct
7 Correct 47 ms 5900 KB Output is correct
8 Correct 110 ms 23740 KB Output is correct
9 Correct 122 ms 23680 KB Output is correct
10 Correct 37 ms 5952 KB Output is correct
11 Correct 138 ms 32716 KB Output is correct
12 Correct 116 ms 32636 KB Output is correct
13 Correct 132 ms 32548 KB Output is correct
14 Correct 41 ms 5904 KB Output is correct
15 Correct 115 ms 24132 KB Output is correct
16 Correct 163 ms 24636 KB Output is correct
17 Correct 145 ms 25064 KB Output is correct
18 Correct 137 ms 25148 KB Output is correct
19 Correct 176 ms 29688 KB Output is correct
20 Correct 196 ms 28904 KB Output is correct
21 Correct 113 ms 24176 KB Output is correct
22 Correct 133 ms 24388 KB Output is correct
23 Correct 123 ms 24548 KB Output is correct
24 Correct 121 ms 24648 KB Output is correct
25 Correct 132 ms 26380 KB Output is correct
26 Correct 156 ms 24128 KB Output is correct
27 Correct 119 ms 24232 KB Output is correct

Subtask #12
0.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5976 KB Output is correct
2 Correct 48 ms 6792 KB Output is correct
3 Correct 49 ms 6908 KB Output is correct
4 Correct 48 ms 6904 KB Output is correct
5 Correct 42 ms 7244 KB Output is correct
6 Correct 46 ms 6884 KB Output is correct
7 Correct 47 ms 5900 KB Output is correct
8 Correct 110 ms 23740 KB Output is correct
9 Correct 122 ms 23680 KB Output is correct
10 Correct 37 ms 5952 KB Output is correct
11 Correct 138 ms 32716 KB Output is correct
12 Correct 116 ms 32636 KB Output is correct
13 Correct 132 ms 32548 KB Output is correct
14 Correct 41 ms 5904 KB Output is correct
15 Correct 115 ms 24132 KB Output is correct
16 Correct 163 ms 24636 KB Output is correct
17 Correct 145 ms 25064 KB Output is correct
18 Correct 137 ms 25148 KB Output is correct
19 Correct 176 ms 29688 KB Output is correct
20 Correct 196 ms 28904 KB Output is correct
21 Correct 113 ms 24176 KB Output is correct
22 Correct 133 ms 24388 KB Output is correct
23 Correct 123 ms 24548 KB Output is correct
24 Correct 121 ms 24648 KB Output is correct
25 Correct 132 ms 26380 KB Output is correct
26 Correct 156 ms 24128 KB Output is correct
27 Correct 119 ms 24232 KB Output is correct
28 Partially correct 2 ms 3284 KB Output is incorrect
29 Partially correct 2 ms 3156 KB Output is incorrect
30 Partially correct 3 ms 3284 KB Output is incorrect
31 Partially correct 2 ms 3156 KB Output is incorrect
32 Partially correct 3 ms 3160 KB Output is incorrect
33 Partially correct 2 ms 3156 KB Output is incorrect
34 Partially correct 2 ms 3284 KB Output is incorrect
35 Partially correct 2 ms 3156 KB Output is incorrect
36 Partially correct 2 ms 3156 KB Output is incorrect
37 Partially correct 2 ms 3156 KB Output is incorrect
38 Partially correct 2 ms 3288 KB Output is incorrect
39 Partially correct 2 ms 3160 KB Output is incorrect
40 Partially correct 2 ms 3156 KB Output is incorrect
41 Partially correct 2 ms 3156 KB Output is incorrect
42 Partially correct 2 ms 3156 KB Output is incorrect
43 Partially correct 3 ms 3288 KB Output is incorrect
44 Partially correct 2 ms 3156 KB Output is incorrect
45 Partially correct 25 ms 6764 KB Output is incorrect
46 Partially correct 2 ms 3156 KB Output is incorrect
47 Partially correct 2 ms 3156 KB Output is incorrect
48 Partially correct 3 ms 3156 KB Output is incorrect
49 Partially correct 27 ms 7196 KB Output is incorrect
50 Partially correct 37 ms 8140 KB Output is incorrect
51 Partially correct 2 ms 3156 KB Output is incorrect
52 Partially correct 2 ms 3156 KB Output is incorrect
53 Partially correct 2 ms 3156 KB Output is incorrect
54 Partially correct 2 ms 3160 KB Output is incorrect
55 Partially correct 2 ms 3156 KB Output is incorrect
56 Partially correct 2 ms 3156 KB Output is incorrect
57 Partially correct 2 ms 3156 KB Output is incorrect
58 Partially correct 32 ms 7792 KB Output is incorrect
59 Partially correct 40 ms 9424 KB Output is incorrect