oj.uz

Submission #423876

# Submission time Handle Problem Language Result Execution time Memory
423876 2021-06-11T13:42:38 Z zoooma13 Inside information (BOI21_servers) C++14
50 / 100
 483 ms 39908 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 120005
#define LOG_N 17

struct DSU{
    vector <int> e;
    DSU(int n) : e(n ,-1) {}
    int find(int x) { return e[x]<0? x : e[x]=find(e[x]); }
    int size(int x) { return -e[find(x)]; }
    bool join(int x ,int y){
        x = find(x) ,y = find(y);
        if(x == y) return false;
        if(e[x] > e[y]) swap(x ,y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

struct query{
    int type ,time ,fr ,to;
};

int tin[MAX_N] ,tout[MAX_N] ,tt;
int val[MAX_N] ,dis[MAX_N];
int par[LOG_N][MAX_N] ,inv[LOG_N][MAX_N];
vector <vector <pair<int ,int>>> adj;
void pre(int u){
    tin[u] = ++tt;
    for(int j = 1; (1<<j) <= dis[u]; j++){
        par[j][u] = par[j-1][par[j-1][u]];
        inv[j][u] = inv[j-1][u] + inv[j-1][par[j-1][u]];
    }
//    cout << "at " << u << " val = " << val[u] << " and inv = " << inv[0][u] << endl;
    for(auto&e : adj[u]) if(e.first != par[0][u]){
        val[e.first] = e.second;
        par[0][e.first] = u;
        inv[0][e.first] = e.second > val[u];
        dis[e.first] = dis[u]+1;
        pre(e.first);
    }
    tout[u] = tt;
}
bool isAnc(int u ,int v){ //is u ancestor of v?
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main()
{   int n ,k;
    scanf("%d%d",&n,&k);
    adj.resize(n+1);
    vector <query> qs;
    for(int t = 1; t < n+k; t++){
        char q; int x ,y;
        scanf(" %c%d",&q,&x);
        if(q == 'S'){
            scanf("%d",&y);
            adj[x].push_back({y ,t});
            adj[y].push_back({x ,t});
            qs.push_back({0 ,t ,x ,y});
        }
        else if(q == 'Q'){
            scanf("%d",&y);
            qs.push_back({1 ,t ,x ,y});
        }
        else
            qs.push_back({2 ,t ,x ,-1});
    }

    memset(par ,-1 ,sizeof par);
    par[0][1] = 1;
    pre(1);

    DSU d(n+1);
    for(query&q : qs){
        if(q.type == 0){
            d.join(q.fr ,q.to);
        }
        else if(q.type == 1){
            if(d.find(q.fr) != d.find(q.to))
                printf("no\n");
            else{
                int a = q.to ,b = q.fr;
                for(int j = LOG_N-1; ~j; j--)
                    if(par[j][a] != -1 && inv[j][a] == 0)
                        a = par[j][a];
                for(int j = LOG_N-1; ~j; j--)
                    if(par[j][b] != -1 && inv[j][b] == (1<<j))
                        b = par[j][b];
//                cout << q.to << " can reach " << a << endl;
//                cout << q.fr << " can reach " << b << endl;
                if(dis[a] < dis[b])
                    swap(a ,b);
                a = par[0][a];

                int u = q.to ,v = q.fr;
                for(int j = LOG_N-1; ~j; j--) if((dis[u]-dis[a]-1)>>j&1)
                    u = par[j][u];
                for(int j = LOG_N-1; ~j; j--) if((dis[v]-dis[a]-1)>>j&1)
                    v = par[j][v];

//                cout << "a = " << a << endl;
//                cout << tin[a] << ' ' << tout[a] << endl;
                if(isAnc(a ,q.fr) && isAnc(a ,q.to) && (isAnc(q.fr ,q.to) || isAnc(q.to ,q.fr) || val[u] <= val[v]))
                    printf("yes\n");
                else
                    printf("no\n");
            }
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf(" %c%d",&q,&x);
      |         ~~~~~^~~~~~~~~~~~~~~
servers.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |             scanf("%d",&y);
      |             ~~~~~^~~~~~~~~
servers.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d",&y);
      |             ~~~~~^~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 10804 KB Output is correct
2 Correct 50 ms 12296 KB Output is correct
3 Correct 71 ms 12424 KB Output is correct
4 Correct 51 ms 12644 KB Output is correct
5 Correct 86 ms 12792 KB Output is correct
6 Correct 63 ms 12392 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 10804 KB Output is correct
2 Correct 50 ms 12296 KB Output is correct
3 Correct 71 ms 12424 KB Output is correct
4 Correct 51 ms 12644 KB Output is correct
5 Correct 86 ms 12792 KB Output is correct
6 Correct 63 ms 12392 KB Output is correct
7 Incorrect 55 ms 11452 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10780 KB Output is correct
2 Correct 231 ms 25528 KB Output is correct
3 Correct 233 ms 25644 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10780 KB Output is correct
2 Correct 231 ms 25528 KB Output is correct
3 Correct 233 ms 25644 KB Output is correct
4 Incorrect 45 ms 11472 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10816 KB Output is correct
2 Correct 283 ms 39740 KB Output is correct
3 Correct 247 ms 39728 KB Output is correct
4 Correct 228 ms 39600 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10816 KB Output is correct
2 Correct 283 ms 39740 KB Output is correct
3 Correct 247 ms 39728 KB Output is correct
4 Correct 228 ms 39600 KB Output is correct
5 Incorrect 41 ms 11516 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10836 KB Output is correct
2 Correct 206 ms 27616 KB Output is correct
3 Correct 217 ms 28140 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10836 KB Output is correct
2 Correct 206 ms 27616 KB Output is correct
3 Correct 217 ms 28140 KB Output is correct
4 Incorrect 43 ms 11440 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10928 KB Output is correct
2 Correct 267 ms 39728 KB Output is correct
3 Correct 248 ms 39704 KB Output is correct
4 Correct 243 ms 39656 KB Output is correct
5 Correct 44 ms 11568 KB Output is correct
6 Correct 180 ms 27660 KB Output is correct
7 Correct 220 ms 28116 KB Output is correct
8 Correct 286 ms 31240 KB Output is correct
9 Correct 280 ms 30656 KB Output is correct
10 Correct 483 ms 37868 KB Output is correct
11 Correct 480 ms 37148 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10928 KB Output is correct
2 Correct 267 ms 39728 KB Output is correct
3 Correct 248 ms 39704 KB Output is correct
4 Correct 243 ms 39656 KB Output is correct
5 Correct 44 ms 11568 KB Output is correct
6 Correct 180 ms 27660 KB Output is correct
7 Correct 220 ms 28116 KB Output is correct
8 Correct 286 ms 31240 KB Output is correct
9 Correct 280 ms 30656 KB Output is correct
10 Correct 483 ms 37868 KB Output is correct
11 Correct 480 ms 37148 KB Output is correct
12 Incorrect 64 ms 11440 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11148 KB Output is correct
2 Correct 52 ms 12356 KB Output is correct
3 Correct 72 ms 12348 KB Output is correct
4 Correct 48 ms 12740 KB Output is correct
5 Correct 86 ms 12720 KB Output is correct
6 Correct 62 ms 12344 KB Output is correct
7 Correct 47 ms 11496 KB Output is correct
8 Correct 229 ms 25684 KB Output is correct
9 Correct 218 ms 25548 KB Output is correct
10 Correct 48 ms 11572 KB Output is correct
11 Correct 292 ms 39708 KB Output is correct
12 Correct 263 ms 39908 KB Output is correct
13 Correct 232 ms 39688 KB Output is correct
14 Correct 45 ms 11448 KB Output is correct
15 Correct 187 ms 27684 KB Output is correct
16 Correct 235 ms 28200 KB Output is correct
17 Correct 285 ms 31204 KB Output is correct
18 Correct 286 ms 30592 KB Output is correct
19 Correct 322 ms 37924 KB Output is correct
20 Correct 405 ms 37176 KB Output is correct
21 Correct 230 ms 26556 KB Output is correct
22 Correct 209 ms 26676 KB Output is correct
23 Correct 262 ms 28692 KB Output is correct
24 Correct 251 ms 29348 KB Output is correct
25 Correct 324 ms 34924 KB Output is correct
26 Correct 240 ms 28124 KB Output is correct
27 Correct 196 ms 27972 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11148 KB Output is correct
2 Correct 52 ms 12356 KB Output is correct
3 Correct 72 ms 12348 KB Output is correct
4 Correct 48 ms 12740 KB Output is correct
5 Correct 86 ms 12720 KB Output is correct
6 Correct 62 ms 12344 KB Output is correct
7 Correct 47 ms 11496 KB Output is correct
8 Correct 229 ms 25684 KB Output is correct
9 Correct 218 ms 25548 KB Output is correct
10 Correct 48 ms 11572 KB Output is correct
11 Correct 292 ms 39708 KB Output is correct
12 Correct 263 ms 39908 KB Output is correct
13 Correct 232 ms 39688 KB Output is correct
14 Correct 45 ms 11448 KB Output is correct
15 Correct 187 ms 27684 KB Output is correct
16 Correct 235 ms 28200 KB Output is correct
17 Correct 285 ms 31204 KB Output is correct
18 Correct 286 ms 30592 KB Output is correct
19 Correct 322 ms 37924 KB Output is correct
20 Correct 405 ms 37176 KB Output is correct
21 Correct 230 ms 26556 KB Output is correct
22 Correct 209 ms 26676 KB Output is correct
23 Correct 262 ms 28692 KB Output is correct
24 Correct 251 ms 29348 KB Output is correct
25 Correct 324 ms 34924 KB Output is correct
26 Correct 240 ms 28124 KB Output is correct
27 Correct 196 ms 27972 KB Output is correct
28 Incorrect 46 ms 11500 KB Extra information in the output file
29 Halted 0 ms 0 KB -