oj.uz

Submission #812914

# Submission time Handle Problem Language Result Execution time Memory
812914 2023-08-07T11:47:49 Z Ronin13 Inside information (BOI21_servers) C++17
60 / 100
 532 ms 128372 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <bitset>
#include <vector>
#include <set>
#include <bitset>
#include <map>

#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
const int nmax = 2000001;

vector <vector <int> > g(nmax);
int p[nmax][22];
int val[nmax][22];
bool inc[nmax][22], dc[nmax][22];
int d[nmax];
map <pii, int> vv;
int timer = 0;
int in[nmax], out[nmax];

void dfs(int v, int e){
    p[v][0] = e;
    in[v] = timer++;
    inc[v][0] = dc[v][0] = true;
    for(int i = 1; i <= 20; i++){
        inc[v][i] = inc[v][i - 1];
        dc[v][i] = dc[v][i - 1];
        p[v][i] = p[p[v][i - 1]][i - 1];
        val[v][i] = val[p[v][i - 1]][i - 1];
        inc[v][i] &= inc[p[v][i - 1]][i - 1];
        if(p[v][i - 1] != 1)inc[v][i] &= (val[v][i - 1] < val[p[v][i - 1]][0]);
        dc[v][i] &= dc[p[v][i - 1]][i - 1];
        if(p[v][i - 1] != 1) dc[v][i] &= (val[v][i - 1] > val[p[v][i- 1]][0]);
    }
    for(int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if(to == e) continue;
        d[to] = d[v] + 1;
        val[to][0] = vv[mp(v, to)];
        dfs(to, v);
    }
    out[v] = timer++;
}

bool isanc(int u, int v){
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v){
    if(isanc(u, v)) return u;
    if(isanc(v, u)) return v;
    for(int j = 20; j >= 0; j--){
        if(!isanc(p[u][j], v)) 
            u = p[u][j];
    }
    return p[u][0];
}

pair<int,bool> lift_inc(int u, int d){
    int lst = -1e9;
    bool good = true;
    while(d){
        int x = log2(d);
        if(lst > val[u][0]) good = false;
        good &= inc[u][x];
        lst = val[u][x];
        d -= (1 << x);
        u = p[u][x];
    }
    return mp(lst, good);
}
pair<int, bool> lift_dec(int u, int d){
    int lst = 1e9;
    bool good = true;
    while(d){
        int x = log2(d);
        if(lst < val[u][0]) good = false;
        good &= dc[u][x];
        lst = val[u][x];
        u = p[u][x];
        d -= (1 << x);
    }
    return mp(lst, good);
}

bool getans(int u, int v){
    int x = lca(u, v);
    pii o = lift_inc(u, d[u] - d[x]);
    pii oo = lift_dec(v, d[v] - d[x]);
    //cout << o.f << ' ' << oo.f << "\n";
    return o.s && oo.s && o.f < oo.f;
}

bool isstored[4001][4001];
int ans[4001];

vector <int> bit(nmax);

int lsb(int x){
    return x & -x;
}

void add(int pos, int val){
    while(pos < nmax){
        bit[pos] += val;
        pos += lsb(pos);
    }
}

int gg(int pos){
    int res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

int P[nmax], Sz[nmax];

void make_set(int v){
    P[v] = v;
    Sz[v] = 1;
}

int find_set(int v){
    return P[v] == v ? v : P[v] = find_set(P[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
     b =find_set(b);
     if(Sz[a] < Sz[b]) swap(a, b);
     P[b] = a;
     Sz[a] += Sz[b];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    int deg[n + 1];
    for(int i = 1; i <= n; i++){
        deg[i] = 0;
        if(n <= 4000){isstored[i][i] = true;
        ans[i] = 1;}
    }
   m += n - 1;
    vector <pair<char, vector <int> > >query(m + 1);
   if(n <= 4000){
        for(int i= 1; i <= m; i++){
            char c; cin >> c;
            if(c == 'S'){
                int u, v; cin >> u >> v;
                for(int j = 1; j <= n ;j++) {
                    ans[j] -= (int)isstored[u][j];
                    ans[j] -= (int)isstored[v][j];
                    isstored[u][j] |= isstored[v][j], isstored[v][j] |= isstored[u][j];
                    ans[j] += (int)isstored[u][j];
                    ans[j] += (int)isstored[v][j];
                }
            }
            if(c == 'Q'){
                int a, d; cin >> a >> d;
                if(isstored[a][d]) cout << "yes\n";
                else cout << "no\n";
            }
            if(c == 'C'){
                int x; cin >> x;
                cout << ans[x] << "\n";
            }
        }
        return 0;
    }
    bool kk = true;
    for(int i = 1; i <= m; i++){
        char c; cin >> c;
        vector <int> x;
        if(c == 'S'){
            int u, v; cin >> u >> v;
            if(abs(u - v) > 1) kk = false;
            x.pb(u); x.pb(v);
            g[u].pb(v);
            g[v].pb(u);
            deg[u]++;
            deg[v]++;
            vv[mp(u, v)] = vv[mp(v, u)] = i;
        }
        if(c == 'Q'){
            int a, d; cin >> a >> d;
            x.pb(a); x.pb(d);
        }
        if(c == 'C'){
            int a; cin >> a;
            x.pb(a);
        }
        query[i] = mp(c, x);
    }
    if(kk){
        int l[n + 1], r[n + 1];
        for(int i = 1; i <= n; i++){
            l[i] = r[i] = i;
            add(l[i], 1);
            add(l[i] + 1, -1);
        }
        for(int i = 1; i <= m; i++){
            char c = query[i].f;
            if(c == 'S'){
                int a, b; 
                a = query[i].s[0];
                b = query[i].s[1];
                add(l[a], -1);
                add(r[a] + 1, 1);
                add(l[b], -1);
                add(r[b] + 1, 1);
                int L = min(l[a], l[b]);
                int R = max(r[a], r[b]);
                l[a] = l[b] = L;
                r[a] = r[b] = R;
                add(l[a], 1);
                add(r[a] + 1, -1);
                add(l[b], 1);
                add(r[b] + 1, -1);
            }
            if(c == 'Q'){
                int a, d; 
                a =query[i].s[0], d = query[i].s[1];
                if(l[a] <= d && r[a] >= d) cout << "yes\n";
                else cout << "no\n";
            }
            if(c == 'C'){
                int x = query[i].s[0];
                cout << gg(x) << "\n";
            }
        }
        return 0;
    }
    if(deg[1] == n - 1){
        for(int i = 1; i <= m ;i++){
            char c = query[i].f;
            if(c == 'S'){
                int a, b; 
                a = query[i].s[0];
                b = query[i].s[1];
                b = max(a, b);
                in[b] = ++timer;
            }
            if(c == 'Q'){
                int a, d; 
                a= query[i].s[0];
                d = query[i].s[1];
                if(a == d){
                    cout << "yes\n";
                    continue;
                }
                if(d == 1){
                    if(in[a]) cout << "yes\n";
                    else cout << "no\n";
                }
                else{
                    if(in[d] == 0) cout << "no" << "\n";
                    else{
                        if(a == 1 || in[a] > in[d]) cout << "yes\n";
                        else cout << "no\n";
                    }
                }
            }
            if(c == 'C'){
                int x;
                x = query[i].s[0];
                if(x == 1){
                    cout << timer +1 << "\n";
                    continue;
                }
                if(in[x] == 0) cout << 1 << "\n";
                else{
                    cout << timer - in[x] + 2 << "\n";
                }
            }
        }
        return 0;
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++)
        make_set(i);
    
    for(int i = 1; i <= m; i++){
        char c = query[i].f;
        if(c == 'S'){
            int a = query[i].s[0], b = query[i].s[1];
            union_sets(a, b);
        }
        if(c == 'Q'){
            int a = query[i].s[0], b = query[i].s[1];
            if(find_set(a) == find_set(b) && getans(b, a)) cout << "yes\n";
            else cout << "no\n";
        }
        if(c == 'C'){
            cout << 0 << "\n";
        }
    }
    return 0;
}

Compilation message

servers.cpp:24: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      | 
servers.cpp: In function 'void dfs(int, int)':
servers.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < g[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60236 KB Output is correct
2 Correct 80 ms 76448 KB Output is correct
3 Correct 83 ms 76484 KB Output is correct
4 Correct 84 ms 76396 KB Output is correct
5 Correct 80 ms 76360 KB Output is correct
6 Correct 80 ms 76424 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60236 KB Output is correct
2 Correct 80 ms 76448 KB Output is correct
3 Correct 83 ms 76484 KB Output is correct
4 Correct 84 ms 76396 KB Output is correct
5 Correct 80 ms 76360 KB Output is correct
6 Correct 80 ms 76424 KB Output is correct
7 Correct 42 ms 60280 KB Output is correct
8 Correct 81 ms 76020 KB Output is correct
9 Correct 79 ms 76236 KB Output is correct
10 Correct 80 ms 76096 KB Output is correct
11 Correct 79 ms 76104 KB Output is correct
12 Correct 94 ms 76272 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 60376 KB Output is correct
2 Correct 222 ms 93636 KB Output is correct
3 Correct 230 ms 93544 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 60376 KB Output is correct
2 Correct 222 ms 93636 KB Output is correct
3 Correct 230 ms 93544 KB Output is correct
4 Correct 42 ms 60236 KB Output is correct
5 Correct 233 ms 93432 KB Output is correct
6 Correct 221 ms 92752 KB Output is correct
7 Correct 220 ms 92848 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 60256 KB Output is correct
2 Correct 243 ms 94044 KB Output is correct
3 Correct 245 ms 94028 KB Output is correct
4 Correct 189 ms 93928 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 60256 KB Output is correct
2 Correct 243 ms 94044 KB Output is correct
3 Correct 245 ms 94028 KB Output is correct
4 Correct 189 ms 93928 KB Output is correct
5 Correct 41 ms 60268 KB Output is correct
6 Correct 257 ms 93652 KB Output is correct
7 Correct 175 ms 93800 KB Output is correct
8 Correct 237 ms 93248 KB Output is correct
9 Correct 238 ms 93228 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60276 KB Output is correct
2 Correct 242 ms 121208 KB Output is correct
3 Correct 356 ms 121272 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60276 KB Output is correct
2 Correct 242 ms 121208 KB Output is correct
3 Correct 356 ms 121272 KB Output is correct
4 Correct 43 ms 60228 KB Output is correct
5 Incorrect 219 ms 120880 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60244 KB Output is correct
2 Correct 260 ms 94084 KB Output is correct
3 Correct 233 ms 94060 KB Output is correct
4 Correct 185 ms 93972 KB Output is correct
5 Correct 41 ms 60240 KB Output is correct
6 Correct 254 ms 121260 KB Output is correct
7 Correct 324 ms 121372 KB Output is correct
8 Correct 433 ms 121828 KB Output is correct
9 Correct 372 ms 121768 KB Output is correct
10 Correct 403 ms 128356 KB Output is correct
11 Correct 428 ms 126908 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60244 KB Output is correct
2 Correct 260 ms 94084 KB Output is correct
3 Correct 233 ms 94060 KB Output is correct
4 Correct 185 ms 93972 KB Output is correct
5 Correct 41 ms 60240 KB Output is correct
6 Correct 254 ms 121260 KB Output is correct
7 Correct 324 ms 121372 KB Output is correct
8 Correct 433 ms 121828 KB Output is correct
9 Correct 372 ms 121768 KB Output is correct
10 Correct 403 ms 128356 KB Output is correct
11 Correct 428 ms 126908 KB Output is correct
12 Correct 50 ms 60224 KB Output is correct
13 Correct 256 ms 93580 KB Output is correct
14 Correct 179 ms 93688 KB Output is correct
15 Correct 284 ms 93144 KB Output is correct
16 Correct 243 ms 93196 KB Output is correct
17 Correct 44 ms 60280 KB Output is correct
18 Incorrect 224 ms 120852 KB Extra information in the output file
19 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 60280 KB Output is correct
2 Correct 82 ms 76340 KB Output is correct
3 Correct 79 ms 76480 KB Output is correct
4 Correct 98 ms 76416 KB Output is correct
5 Correct 92 ms 76340 KB Output is correct
6 Correct 84 ms 76416 KB Output is correct
7 Correct 40 ms 60324 KB Output is correct
8 Correct 227 ms 93548 KB Output is correct
9 Correct 280 ms 93568 KB Output is correct
10 Correct 41 ms 60232 KB Output is correct
11 Correct 268 ms 94116 KB Output is correct
12 Correct 249 ms 94100 KB Output is correct
13 Correct 185 ms 93956 KB Output is correct
14 Correct 41 ms 60336 KB Output is correct
15 Correct 253 ms 121264 KB Output is correct
16 Correct 386 ms 121332 KB Output is correct
17 Correct 492 ms 121856 KB Output is correct
18 Correct 532 ms 121788 KB Output is correct
19 Correct 424 ms 128372 KB Output is correct
20 Correct 481 ms 127012 KB Output is correct
21 Correct 388 ms 121900 KB Output is correct
22 Correct 386 ms 121912 KB Output is correct
23 Correct 378 ms 121980 KB Output is correct
24 Correct 384 ms 122060 KB Output is correct
25 Correct 433 ms 126944 KB Output is correct
26 Correct 332 ms 121652 KB Output is correct
27 Correct 327 ms 121652 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 60280 KB Output is correct
2 Correct 82 ms 76340 KB Output is correct
3 Correct 79 ms 76480 KB Output is correct
4 Correct 98 ms 76416 KB Output is correct
5 Correct 92 ms 76340 KB Output is correct
6 Correct 84 ms 76416 KB Output is correct
7 Correct 40 ms 60324 KB Output is correct
8 Correct 227 ms 93548 KB Output is correct
9 Correct 280 ms 93568 KB Output is correct
10 Correct 41 ms 60232 KB Output is correct
11 Correct 268 ms 94116 KB Output is correct
12 Correct 249 ms 94100 KB Output is correct
13 Correct 185 ms 93956 KB Output is correct
14 Correct 41 ms 60336 KB Output is correct
15 Correct 253 ms 121264 KB Output is correct
16 Correct 386 ms 121332 KB Output is correct
17 Correct 492 ms 121856 KB Output is correct
18 Correct 532 ms 121788 KB Output is correct
19 Correct 424 ms 128372 KB Output is correct
20 Correct 481 ms 127012 KB Output is correct
21 Correct 388 ms 121900 KB Output is correct
22 Correct 386 ms 121912 KB Output is correct
23 Correct 378 ms 121980 KB Output is correct
24 Correct 384 ms 122060 KB Output is correct
25 Correct 433 ms 126944 KB Output is correct
26 Correct 332 ms 121652 KB Output is correct
27 Correct 327 ms 121652 KB Output is correct
28 Correct 42 ms 60236 KB Output is correct
29 Correct 81 ms 76060 KB Output is correct
30 Correct 79 ms 76212 KB Output is correct
31 Correct 84 ms 76004 KB Output is correct
32 Correct 80 ms 76076 KB Output is correct
33 Correct 80 ms 76280 KB Output is correct
34 Correct 42 ms 60272 KB Output is correct
35 Correct 219 ms 93480 KB Output is correct
36 Correct 224 ms 92764 KB Output is correct
37 Correct 219 ms 92824 KB Output is correct
38 Correct 43 ms 60288 KB Output is correct
39 Correct 260 ms 93636 KB Output is correct
40 Correct 173 ms 93752 KB Output is correct
41 Correct 244 ms 93132 KB Output is correct
42 Correct 242 ms 93232 KB Output is correct
43 Correct 42 ms 60236 KB Output is correct
44 Incorrect 221 ms 120784 KB Extra information in the output file
45 Halted 0 ms 0 KB -