제출 #813511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813511		Ronin13	Inside information (BOI21_servers)	C++17	5 / 100	516 ms	353560 KiB

servers

#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, lst, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5