oj.uz

Submission #813524

# Submission time Handle Problem Language Result Execution time Memory
813524 2023-08-07T19:31:02 Z Ronin13 Inside information (BOI21_servers) C++17
100 / 100
 801 ms 420960 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 <pii> > g(nmax);

struct fenwick{ 
    int n;
    vector <int> bit;
    fenwick(){
        n = 0;
    }
    fenwick(int n) : n(n){
        bit.resize(n + 1);
    }
    void add(int pos, int val){
        while(pos <= n){
            bit[pos] += val;
            pos += (pos & -pos);
        }
    }
    int get(int pos){
        int res = 0;
        while(pos){
            res += bit[pos];
            pos -= (pos & -pos);
        }
        return res;
    }
    int sum(int l, int r){
        return get(r) - get(l - 1);
    }
}fen[nmax];

int sz[nmax];
vector <bool> marked(nmax);

void dfs(int v, int e){
    sz[v] = 0;
    for(auto x : g[v]){
        int to = x.f;
        if(marked[to] || to == e) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
    sz[v]++;
}

int find_cent(int v, int n, int e){
    if(sz[v] * 2 < n) return 0;
    for(auto x : g[v]){
        int to = x.f;
        if(marked[to] || to == e) continue;
        int y = find_cent(to, n, v);
        if(y) return y;
    }
    return v;
}

multiset <pii> st[nmax];
vector <vector <pii> > vec(nmax);
vector <vector <pii> > cc(nmax);

int c;
void DFS(int v, int e, int lst, bool inc, bool dc, int ind){
    if(inc){
        st[c].insert(mp(lst, ind));
        vec[v].pb(mp(c, ind));
    }
    if(dc){
        cc[v].pb(mp(c, ind));
    }
    for(auto x : g[v]){
        int to = x.f; int len = x.s;
        bool ndc, ninc;
        ndc = dc, ninc = inc;
        if(marked[to] || to == e) continue;
        if(len > lst) ndc = false;
        if(len < lst) ninc = false;
        DFS(to, v, len, ninc, ndc, ind);
    }
}

void decompose(int v){
    dfs(v, v);
    int x= find_cent(v, sz[v], v);
    st[x].insert({0, 1});
    cc[x].pb({x, 1});
    vec[x].pb({x, 1e9});
    int cur = 2;
    c = x;
    marked[x] = true;
    //cout << x << ' ';
    for(auto ed : g[x]){
        int to = ed.f;
        if(marked[to]) continue;
        DFS(to, x, ed.s, true, true, cur);
        cur++;
    }
    st[x].insert({0, cur});
    fen[x] = {cur};
    for(auto ed : g[x]){
        if(!marked[ed.f])
            decompose(ed.f);
    }
}

bool Query(int a, int b){
    for(auto x : vec[a]){
        for(auto y : cc[b]){
            if(x.f == y.f && x.s != y.s){
                if(x.s > y.s) return true;
                return false;
            }
        }
    }
    return false;
}

vector <int> p(nmax), s(nmax);

void make_set(int v){
    p[v] = v;s[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(s[a] < s[b]) swap(a, b);
    p[b] = a;
    s[a] += s[b];
}

int Count(int a, int t){
    ll ans = 0;
    for(auto x : cc[a]){
        int v = x.f;
        if(find_set(v) != find_set(a)) continue;
        while(!st[v].empty()){
            int x = st[v].begin()->f;
            if(x < t) {
                fen[v].add(st[v].begin()->s, 1);
                st[v].erase(st[v].begin());
            }
            else break;
        }
        ans += fen[v].sum(x.s + 1, fen[v].n);
    }
    return ans;
}



int main(){
    int n; cin >> n;
    int m; cin >> m;
    vector <pair<char, pii> > query(n + m );
    m += n - 1;
    for(int i= 1; i <= n; i++){
        make_set(i);
    }
    for(int i = 1; i <= m; i++){
        char c; cin >> c;
        if(c == 'S'){
            int a, b; cin >> a >> b;
            g[a].pb({b, i});
            g[b].pb({a, i});
            query[i] = {c, {a, b}};
        }
        if(c == 'Q'){
            int a, d; cin >> a >> d;
            query[i] = {c, {a, d}};
        }
        if(c == 'C'){
            int a; cin >> a;
            query[i] = {c, {a, a}};
        }
    }
    decompose(1);
    for(int i = 1; i <= m; i++){
        if(query[i].f == 'S'){
            union_sets(query[i].s.f, query[i].s.s);
            continue;
        }
        if(query[i].f == 'Q'){
            int a = query[i].s.f, d = query[i].s.s;
            if(Query(a, d) && find_set(a) == find_set(d)) cout << "yes\n";
            else cout << "no\n";
        }
        if(query[i].f == 'C'){
            int a = query[i].s.f;
            cout << Count(a, i) << '\n';
        }
    }
    return 0;
}

Compilation message

servers.cpp:24: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 315528 KB Output is correct
2 Correct 204 ms 318084 KB Output is correct
3 Correct 209 ms 318128 KB Output is correct
4 Correct 189 ms 318160 KB Output is correct
5 Correct 187 ms 318384 KB Output is correct
6 Correct 184 ms 317988 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 315528 KB Output is correct
2 Correct 204 ms 318084 KB Output is correct
3 Correct 209 ms 318128 KB Output is correct
4 Correct 189 ms 318160 KB Output is correct
5 Correct 187 ms 318384 KB Output is correct
6 Correct 184 ms 317988 KB Output is correct
7 Correct 181 ms 316320 KB Output is correct
8 Correct 184 ms 317756 KB Output is correct
9 Correct 180 ms 317952 KB Output is correct
10 Correct 197 ms 317808 KB Output is correct
11 Correct 185 ms 318048 KB Output is correct
12 Correct 202 ms 317744 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 167 ms 315600 KB Output is correct
2 Correct 488 ms 350756 KB Output is correct
3 Correct 439 ms 350828 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 167 ms 315600 KB Output is correct
2 Correct 488 ms 350756 KB Output is correct
3 Correct 439 ms 350828 KB Output is correct
4 Correct 175 ms 315592 KB Output is correct
5 Correct 457 ms 350756 KB Output is correct
6 Correct 383 ms 351124 KB Output is correct
7 Correct 388 ms 350948 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 315796 KB Output is correct
2 Correct 458 ms 366156 KB Output is correct
3 Correct 467 ms 366144 KB Output is correct
4 Correct 503 ms 420888 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 315796 KB Output is correct
2 Correct 458 ms 366156 KB Output is correct
3 Correct 467 ms 366144 KB Output is correct
4 Correct 503 ms 420888 KB Output is correct
5 Correct 189 ms 316216 KB Output is correct
6 Correct 472 ms 365656 KB Output is correct
7 Correct 538 ms 417956 KB Output is correct
8 Correct 487 ms 365268 KB Output is correct
9 Correct 471 ms 365260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 315752 KB Output is correct
2 Correct 532 ms 399488 KB Output is correct
3 Correct 456 ms 359744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 315752 KB Output is correct
2 Correct 532 ms 399488 KB Output is correct
3 Correct 456 ms 359744 KB Output is correct
4 Correct 168 ms 316236 KB Output is correct
5 Correct 513 ms 399128 KB Output is correct
6 Correct 475 ms 359328 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 315724 KB Output is correct
2 Correct 493 ms 366120 KB Output is correct
3 Correct 470 ms 366096 KB Output is correct
4 Correct 509 ms 420960 KB Output is correct
5 Correct 176 ms 316352 KB Output is correct
6 Correct 526 ms 399528 KB Output is correct
7 Correct 429 ms 359796 KB Output is correct
8 Correct 527 ms 359620 KB Output is correct
9 Correct 488 ms 359716 KB Output is correct
10 Correct 587 ms 387828 KB Output is correct
11 Correct 568 ms 387160 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 315724 KB Output is correct
2 Correct 493 ms 366120 KB Output is correct
3 Correct 470 ms 366096 KB Output is correct
4 Correct 509 ms 420960 KB Output is correct
5 Correct 176 ms 316352 KB Output is correct
6 Correct 526 ms 399528 KB Output is correct
7 Correct 429 ms 359796 KB Output is correct
8 Correct 527 ms 359620 KB Output is correct
9 Correct 488 ms 359716 KB Output is correct
10 Correct 587 ms 387828 KB Output is correct
11 Correct 568 ms 387160 KB Output is correct
12 Correct 170 ms 316204 KB Output is correct
13 Correct 493 ms 365704 KB Output is correct
14 Correct 531 ms 417904 KB Output is correct
15 Correct 468 ms 365228 KB Output is correct
16 Correct 512 ms 365208 KB Output is correct
17 Correct 171 ms 316312 KB Output is correct
18 Correct 517 ms 399192 KB Output is correct
19 Correct 511 ms 359340 KB Output is correct
20 Correct 503 ms 359312 KB Output is correct
21 Correct 513 ms 359344 KB Output is correct
22 Correct 624 ms 386404 KB Output is correct
23 Correct 755 ms 403228 KB Output is correct
24 Correct 735 ms 399180 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 172 ms 315756 KB Output is correct
2 Correct 190 ms 318080 KB Output is correct
3 Correct 187 ms 318128 KB Output is correct
4 Correct 189 ms 318180 KB Output is correct
5 Correct 195 ms 318400 KB Output is correct
6 Correct 185 ms 317972 KB Output is correct
7 Correct 182 ms 316348 KB Output is correct
8 Correct 431 ms 353484 KB Output is correct
9 Correct 444 ms 353464 KB Output is correct
10 Correct 172 ms 316460 KB Output is correct
11 Correct 455 ms 366164 KB Output is correct
12 Correct 464 ms 366104 KB Output is correct
13 Correct 537 ms 420884 KB Output is correct
14 Correct 184 ms 316236 KB Output is correct
15 Correct 482 ms 399476 KB Output is correct
16 Correct 466 ms 359760 KB Output is correct
17 Correct 509 ms 359596 KB Output is correct
18 Correct 492 ms 359676 KB Output is correct
19 Correct 576 ms 387868 KB Output is correct
20 Correct 588 ms 387276 KB Output is correct
21 Correct 466 ms 356872 KB Output is correct
22 Correct 502 ms 356500 KB Output is correct
23 Correct 503 ms 359660 KB Output is correct
24 Correct 501 ms 360012 KB Output is correct
25 Correct 558 ms 361008 KB Output is correct
26 Correct 597 ms 362776 KB Output is correct
27 Correct 547 ms 363816 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 172 ms 315756 KB Output is correct
2 Correct 190 ms 318080 KB Output is correct
3 Correct 187 ms 318128 KB Output is correct
4 Correct 189 ms 318180 KB Output is correct
5 Correct 195 ms 318400 KB Output is correct
6 Correct 185 ms 317972 KB Output is correct
7 Correct 182 ms 316348 KB Output is correct
8 Correct 431 ms 353484 KB Output is correct
9 Correct 444 ms 353464 KB Output is correct
10 Correct 172 ms 316460 KB Output is correct
11 Correct 455 ms 366164 KB Output is correct
12 Correct 464 ms 366104 KB Output is correct
13 Correct 537 ms 420884 KB Output is correct
14 Correct 184 ms 316236 KB Output is correct
15 Correct 482 ms 399476 KB Output is correct
16 Correct 466 ms 359760 KB Output is correct
17 Correct 509 ms 359596 KB Output is correct
18 Correct 492 ms 359676 KB Output is correct
19 Correct 576 ms 387868 KB Output is correct
20 Correct 588 ms 387276 KB Output is correct
21 Correct 466 ms 356872 KB Output is correct
22 Correct 502 ms 356500 KB Output is correct
23 Correct 503 ms 359660 KB Output is correct
24 Correct 501 ms 360012 KB Output is correct
25 Correct 558 ms 361008 KB Output is correct
26 Correct 597 ms 362776 KB Output is correct
27 Correct 547 ms 363816 KB Output is correct
28 Correct 175 ms 316308 KB Output is correct
29 Correct 190 ms 317796 KB Output is correct
30 Correct 190 ms 317932 KB Output is correct
31 Correct 194 ms 317816 KB Output is correct
32 Correct 192 ms 318048 KB Output is correct
33 Correct 185 ms 317824 KB Output is correct
34 Correct 172 ms 316284 KB Output is correct
35 Correct 427 ms 353416 KB Output is correct
36 Correct 446 ms 352752 KB Output is correct
37 Correct 411 ms 352756 KB Output is correct
38 Correct 182 ms 316324 KB Output is correct
39 Correct 487 ms 365616 KB Output is correct
40 Correct 544 ms 417972 KB Output is correct
41 Correct 543 ms 365236 KB Output is correct
42 Correct 497 ms 365240 KB Output is correct
43 Correct 187 ms 316272 KB Output is correct
44 Correct 522 ms 399176 KB Output is correct
45 Correct 494 ms 359372 KB Output is correct
46 Correct 511 ms 359228 KB Output is correct
47 Correct 539 ms 359244 KB Output is correct
48 Correct 624 ms 386380 KB Output is correct
49 Correct 801 ms 403208 KB Output is correct
50 Correct 710 ms 399276 KB Output is correct
51 Correct 462 ms 357284 KB Output is correct
52 Correct 413 ms 353540 KB Output is correct
53 Correct 441 ms 353136 KB Output is correct
54 Correct 422 ms 353856 KB Output is correct
55 Correct 444 ms 354640 KB Output is correct
56 Correct 489 ms 359624 KB Output is correct
57 Correct 561 ms 360544 KB Output is correct
58 Correct 563 ms 361428 KB Output is correct
59 Correct 524 ms 363488 KB Output is correct