oj.uz

Submission #406363

# Submission time Handle Problem Language Result Execution time Memory
406363 2021-05-17T13:10:03 Z mat_v Inside information (BOI21_servers) C++14
50 / 100
 721 ms 62784 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define N 120005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct upit{
    int idx;
    int x,y;
};
vector<upit> v;
int n,k;

vector<pii> graf[N];
map<pii,int> edge;

int br = 1;
int cale[N][20];
int good[N];
int suma[N][20];

int disc[N];
int out[N];


void dfs(int x, int y){
    disc[x] = br;
    cale[x][0] = y;
    if(edge[{y,cale[y][0]}] > edge[{x,y}])good[x] = 1;
    suma[x][0] = good[x];
    ff(j,1,17){
        cale[x][j] = cale[cale[x][j - 1]][j - 1];
        suma[x][j] = suma[x][j - 1] + suma[cale[x][j - 1]][j - 1];
    }
    for(auto c:graf[x]){
        if(c.xx == y)continue;
        br++;
        dfs(c.xx, x);
    }
    br++;
    out[x] = br;
}

bool insubtree(int x, int y){
    if(y == 0)return 1;
    if(x == 0)return 0;
    if(disc[x] >= disc[y] && disc[x] < out[y])return 1;
    return 0;
}
int lca(int x, int y){
    if(insubtree(y,x))return x;
    fb(j,17,0)if(!insubtree(y,cale[x][j]))x = cale[x][j];
    return cale[x][0];
}
int dist(int x, int y){
    if(x == y)return 0;
    int ans = 0;
    fb(j,17,0){
        if(!insubtree(y,cale[x][j])){
            x = cale[x][j];
            ans += (1<<j);
        }
    }
    ans++;
    return ans;
}
int koji(int x, int duz){
    if(duz == 0)return x;
    fb(j,17,0)if((1<<j)&duz)x = cale[x][j];
    return x;
}
int sumado(int x, int duz){
    int ans = 0;
    fb(j,17,0){if((1<<j)&duz){ans += suma[x][j]; x = cale[x][j]; }}
    ans += suma[x][0];
    return ans;
}




int dsu[N];
int sajz[N];
int findpar(int x){
    if(x == dsu[x])return x;
    return dsu[x] = findpar(dsu[x]);
}
void unite(int a, int b){
    a = findpar(a);
    b = findpar(b);
    if(a == b)return;
    if(sajz[a] < sajz[b])swap(a,b);
    dsu[a] = b;
    sajz[b] += sajz[a];
}



int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> k;
    int dsd = 1;
    ff(i,1,n + k - 1){
        char t;
        cin >> t;
        int x,y;
        cin >> x >> y;
        if(t == 'S'){
            graf[x].pb({y,dsd});
            graf[y].pb({x,dsd});
            edge[{x,y}] = edge[{y,x}] = dsd;
            dsd++;
            v.pb({0,x,y});
        }
        else v.pb({1,x,y});
    }
    dfs(1,0);
    ff(i,1,n){dsu[i] = i; sajz[i] = 1;}
    for(auto c:v){
        if(c.idx == 0){
            unite(c.x, c.y);
            continue;
        }
        if(findpar(c.x) != findpar(c.y)){
            cout << "no\n";
            continue;
        }
        int brat = lca(c.x, c.y);
        int l1 = dist(c.x, brat);
        int l2 = dist(c.y, brat);
        int e1 = 1e9;
        int e2 = -1e9;
        bool d1 = 1;
        bool d2 = 1;
        //cout << l1 << " " << l2 << " " << c.x << " " << c.y << " " << brat << "\n";
        if(l1 >= 1)e1 = edge[{brat,koji(c.x,l1-1)}];
        if(l2 >= 1)e2 = edge[{brat,koji(c.y,l2-1)}];
        //cout << e1 << " " << e2 << "\n";
        if(l1 >= 2){
           // cout << sumado(c.x, l1 - 2) << "\n";
            if(sumado(c.x,l1-2) != 0)d1 = 0;
        }
        if(l2 >= 2){
            if(sumado(c.y,l2-2) != l2 - 1)d2 = 0;
        }
        if(d1 == d2 && e1 > e2 && d1 == 1){
            cout << "yes\n";
            continue;
        }
        else cout << "no\n";
    }

    return 0;
}
/*
6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5


*/

Compilation message

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
servers.cpp:46:5: note: in expansion of macro 'ff'
   46 |     ff(j,1,17){
      |     ^~
servers.cpp: In function 'int lca(int, int)':
servers.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
servers.cpp:67:5: note: in expansion of macro 'fb'
   67 |     fb(j,17,0)if(!insubtree(y,cale[x][j]))x = cale[x][j];
      |     ^~
servers.cpp: In function 'int dist(int, int)':
servers.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
servers.cpp:73:5: note: in expansion of macro 'fb'
   73 |     fb(j,17,0){
      |     ^~
servers.cpp: In function 'int koji(int, int)':
servers.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
servers.cpp:84:5: note: in expansion of macro 'fb'
   84 |     fb(j,17,0)if((1<<j)&duz)x = cale[x][j];
      |     ^~
servers.cpp: In function 'int sumado(int, int)':
servers.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
servers.cpp:89:5: note: in expansion of macro 'fb'
   89 |     fb(j,17,0){if((1<<j)&duz){ans += suma[x][j]; x = cale[x][j]; }}
      |     ^~
servers.cpp: In function 'int main()':
servers.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
servers.cpp:121:5: note: in expansion of macro 'ff'
  121 |     ff(i,1,n + k - 1){
      |     ^~
servers.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
servers.cpp:136:5: note: in expansion of macro 'ff'
  136 |     ff(i,1,n){dsu[i] = i; sajz[i] = 1;}
      |     ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5064 KB Output is correct
2 Correct 49 ms 7624 KB Output is correct
3 Correct 88 ms 7676 KB Output is correct
4 Correct 42 ms 7936 KB Output is correct
5 Correct 114 ms 8220 KB Output is correct
6 Correct 93 ms 7656 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5064 KB Output is correct
2 Correct 49 ms 7624 KB Output is correct
3 Correct 88 ms 7676 KB Output is correct
4 Correct 42 ms 7936 KB Output is correct
5 Correct 114 ms 8220 KB Output is correct
6 Correct 93 ms 7656 KB Output is correct
7 Incorrect 13 ms 5148 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 37 ms 5060 KB Output is correct
2 Correct 637 ms 46748 KB Output is correct
3 Correct 595 ms 46764 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5060 KB Output is correct
2 Correct 637 ms 46748 KB Output is correct
3 Correct 595 ms 46764 KB Output is correct
4 Incorrect 13 ms 4992 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 33 ms 5036 KB Output is correct
2 Correct 462 ms 62772 KB Output is correct
3 Correct 424 ms 62760 KB Output is correct
4 Correct 457 ms 62276 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5036 KB Output is correct
2 Correct 462 ms 62772 KB Output is correct
3 Correct 424 ms 62760 KB Output is correct
4 Correct 457 ms 62276 KB Output is correct
5 Incorrect 12 ms 5140 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 35 ms 5052 KB Output is correct
2 Correct 396 ms 50288 KB Output is correct
3 Correct 498 ms 51012 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5052 KB Output is correct
2 Correct 396 ms 50288 KB Output is correct
3 Correct 498 ms 51012 KB Output is correct
4 Incorrect 12 ms 5184 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 33 ms 5024 KB Output is correct
2 Correct 445 ms 62668 KB Output is correct
3 Correct 428 ms 62784 KB Output is correct
4 Correct 462 ms 62332 KB Output is correct
5 Correct 36 ms 5936 KB Output is correct
6 Correct 335 ms 50280 KB Output is correct
7 Correct 508 ms 51016 KB Output is correct
8 Correct 721 ms 51412 KB Output is correct
9 Correct 628 ms 51360 KB Output is correct
10 Correct 603 ms 57188 KB Output is correct
11 Correct 688 ms 56364 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5024 KB Output is correct
2 Correct 445 ms 62668 KB Output is correct
3 Correct 428 ms 62784 KB Output is correct
4 Correct 462 ms 62332 KB Output is correct
5 Correct 36 ms 5936 KB Output is correct
6 Correct 335 ms 50280 KB Output is correct
7 Correct 508 ms 51016 KB Output is correct
8 Correct 721 ms 51412 KB Output is correct
9 Correct 628 ms 51360 KB Output is correct
10 Correct 603 ms 57188 KB Output is correct
11 Correct 688 ms 56364 KB Output is correct
12 Incorrect 14 ms 5108 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 40 ms 4980 KB Output is correct
2 Correct 48 ms 7720 KB Output is correct
3 Correct 95 ms 7796 KB Output is correct
4 Correct 42 ms 7784 KB Output is correct
5 Correct 137 ms 8160 KB Output is correct
6 Correct 95 ms 7748 KB Output is correct
7 Correct 38 ms 5976 KB Output is correct
8 Correct 587 ms 49604 KB Output is correct
9 Correct 564 ms 49512 KB Output is correct
10 Correct 39 ms 5944 KB Output is correct
11 Correct 430 ms 62740 KB Output is correct
12 Correct 458 ms 62748 KB Output is correct
13 Correct 442 ms 62208 KB Output is correct
14 Correct 35 ms 5956 KB Output is correct
15 Correct 323 ms 50224 KB Output is correct
16 Correct 497 ms 51012 KB Output is correct
17 Correct 647 ms 51388 KB Output is correct
18 Correct 629 ms 51444 KB Output is correct
19 Correct 571 ms 57300 KB Output is correct
20 Correct 684 ms 56432 KB Output is correct
21 Correct 682 ms 50500 KB Output is correct
22 Correct 661 ms 50636 KB Output is correct
23 Correct 682 ms 50784 KB Output is correct
24 Correct 622 ms 50992 KB Output is correct
25 Correct 677 ms 53872 KB Output is correct
26 Correct 574 ms 50464 KB Output is correct
27 Correct 440 ms 50600 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4980 KB Output is correct
2 Correct 48 ms 7720 KB Output is correct
3 Correct 95 ms 7796 KB Output is correct
4 Correct 42 ms 7784 KB Output is correct
5 Correct 137 ms 8160 KB Output is correct
6 Correct 95 ms 7748 KB Output is correct
7 Correct 38 ms 5976 KB Output is correct
8 Correct 587 ms 49604 KB Output is correct
9 Correct 564 ms 49512 KB Output is correct
10 Correct 39 ms 5944 KB Output is correct
11 Correct 430 ms 62740 KB Output is correct
12 Correct 458 ms 62748 KB Output is correct
13 Correct 442 ms 62208 KB Output is correct
14 Correct 35 ms 5956 KB Output is correct
15 Correct 323 ms 50224 KB Output is correct
16 Correct 497 ms 51012 KB Output is correct
17 Correct 647 ms 51388 KB Output is correct
18 Correct 629 ms 51444 KB Output is correct
19 Correct 571 ms 57300 KB Output is correct
20 Correct 684 ms 56432 KB Output is correct
21 Correct 682 ms 50500 KB Output is correct
22 Correct 661 ms 50636 KB Output is correct
23 Correct 682 ms 50784 KB Output is correct
24 Correct 622 ms 50992 KB Output is correct
25 Correct 677 ms 53872 KB Output is correct
26 Correct 574 ms 50464 KB Output is correct
27 Correct 440 ms 50600 KB Output is correct
28 Incorrect 14 ms 5184 KB Extra information in the output file
29 Halted 0 ms 0 KB -