Submission #812914

#	Time	Username	Problem	Language	Result	Execution time	Memory
812914		Ronin13	Inside information (BOI21_servers)	C++17	60 / 100	532 ms	128372 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 <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 (stderr)

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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5