Submission #554143

#	Time	Username	Problem	Language	Result	Execution time	Memory
554143		alontanay	Inside information (BOI21_servers)	C++14	50 / 100	258 ms	42756 KiB

servers

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define debug(n) cout << n << endl;
using namespace std;

struct Seg {
    vector<int> seg;
    int n;
    Seg(int n): n(n) {
        seg.resize(2*n);
    }
    void update(int i, int x) {
        i += n;
        seg[i] += x;
        for(i >>= 1; i; i >>= 1) {
            seg[i] = seg[i<<1] + seg[(i<<1)|1];
        }
    }
    int query(int a, int b) {
        int res = 0;
        for(a += n, b += n; a < b; a >>= 1, b >>= 1) {
            if(a&1) {
                res += seg[a++];
            }
            if(b&1) {
                res += seg[--b];
            }
        }
        return res;
    }
};

const int mxN = 120005;

int n, k, q;
vector<pair<char,vector<int>>> input;

//
int cnt[4002];
bool ser[4002][4002];

struct SOL1 {

    SOL1() {
        for(int i = 0; i < 4002; i ++) {
            ser[i][i] = true;
            cnt[i] = 1;
        }
    }

    void Share(int a, int b) {
        for(int d = 1; d < 4002; d ++) {
            if(ser[a][d] ^ ser[b][d]) {
                cnt[d] ++;
                ser[a][d] = ser[b][d] = true;
            }
        }
    }

    bool Query(int a, int d) {
        return ser[a][d];
    }

    int Count(int d) {
        return cnt[d];
    }

};

ll date[120005];
struct SOL2 {
    int cur_date = 1;

    SOL2() {
        date[1] = 1;
    }

    void Share(int a, int b) {
        if(a == 1) { swap(a,b); }
        date[a] = cur_date ++;
    }

    bool Query(int a, int d) {
        if(a == d) { return true; }
        if(date[a]*date[d] == 0) { return false; }
        if(a == 1 || d == 1) {
            return true;
        }
        return date[d] < date[a];
    }

    int Count(int d) {
        if(date[d] == 0) { return 1;}
        if(d == 1) {
            return cur_date;
        }
        return cur_date - date[d] + 1;
    }
};
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector<int> nei[mxN];
int sub[mxN];
int idx[mxN];
int sup[mxN][17];
int depth[mxN];
int dir[mxN];
int cidx = 0;
Seg segUp(mxN);
Seg segDn(mxN);

struct SOLG {
    int cur_date = 1;
    int dfs(int node, int par = -1) {
        idx[node] = cidx ++;
        int sz = 1;
        for(int ne : nei[node]) {
            if(par == ne) { continue; }
            
            depth[ne] = depth[node] + 1;
            sup[ne][0] = node;

            int cur = dfs(ne,node);
            sz += cur;
        }
        return sub[node] = sz;
    }
    int lift(int node, int d) {
        for(int p = 0; p < 17; p ++) {
            if(d&1) { node = sup[node][p]; }
            d /= 2;
        }
        return node;
    }
    void level(int &a, int &b) {
        if(depth[a] < depth[b]) {
            swap(a,b);
        }
        int dif = depth[a] - depth[b];
        a = lift(a,dif);
    }
    int lca(int a, int b) {
        level(a,b);
        if(a == b) { return a; }
        for(int i = 16; i >= 0; i --) {
            if(sup[a][i] != sup[b][i]) {
                a = sup[a][i];
                b = sup[b][i];
            }
        }
        return sup[a][0];
    }
    SOLG() {
        sup[1][0] = 1;
        dfs(1);
        for(int p = 1; p < 17; p ++) {
            for(int i = 1; i <= n; i ++) {
                sup[i][p] = sup[sup[i][p-1]][p-1];
            }
        }
    }

    void Share(int a, int b) {
        if(depth[a] >= depth[b]) { swap(a,b); }
        if(date[a]) {
            segDn.update(idx[b],1);
            segDn.update(idx[b]+sub[b],-1);
            dir[b] = 2;
        }
        for(int ne : nei[b]) {
            if(ne == a) { continue; }
            if(date[ne]) {
                segUp.update(idx[ne],1);
                segUp.update(idx[ne]+sub[ne],-1);
                dir[ne] = 1;
            }
        }
        date[b] = cur_date++;
    }
    bool qUP(int b, int u) {
        int cnt = segUp.query(0,idx[b]+1) - segUp.query(0,idx[u]+1);
        return (cnt == depth[b]-depth[u]);
    }
    bool qDN(int b, int u) {
        int cnt = segDn.query(0,idx[b]+1) - segDn.query(0,idx[u]+1);
        return (cnt == depth[b]-depth[u]);
    }
    bool Query(int a, int d) {
        if(a == d) { return true; }
        if(sup[d][0] == a) { return date[d]; }
        if(sup[a][0] == d) { return date[a]; }

        int c = lca(a,d);
        if(c == a) {
            return qUP(d,lift(d,depth[d]-depth[c]-1));
        }
        if(c == d) {
            return qDN(a,lift(a,depth[a]-depth[c]-1));
        }
        int ca = lift(a,depth[a]-depth[c]-1);
        int cd = lift(d,depth[d]-depth[c]-1);
        bool upSide = qUP(d,cd);
        bool dnSide = qDN(a,ca);
        bool sw = (0 < date[cd] && date[cd] < date[ca]);
        

        return upSide && dnSide && sw;
    }

    int Count(int d) {
        return 0;
    }
};

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void solve1() {
    SOL1 sol1;
    for(pair<char,vector<int>> &Q : input) {
        char t = Q.f;
        int a = Q.s[0], b;
        if(Q.s.size() > 1) { b = Q.s[1]; }
        if(t == 'S') {
            sol1.Share(a,b);
        } else if(t == 'Q') {
            cout << (sol1.Query(a,b) ? "yes\n" : "no\n");
        } else {
            cout << sol1.Count(a) << "\n";
        }
    }
}

void solve2() {
    SOL2 sol2;
    for(pair<char,vector<int>> &Q : input) {
        char t = Q.f;
        int a = Q.s[0], b;
        if(Q.s.size() > 1) { b = Q.s[1]; }
        if(t == 'S') {
            sol2.Share(a,b);
        } else if(t == 'Q') {
            cout << (sol2.Query(a,b) ? "yes\n" : "no\n");
        } else {
            cout << sol2.Count(a) << "\n";
        }
    }
}

void solveG() {
    SOLG solG;
    for(pair<char,vector<int>> &Q : input) {
        char t = Q.f;
        int a = Q.s[0], b;
        if(Q.s.size() > 1) { b = Q.s[1]; }
        if(t == 'S') {
            solG.Share(a,b);
        } else if(t == 'Q') {
            cout << (solG.Query(a,b) ? "yes\n" : "no\n");
        } else {
            cout << solG.Count(a) << "\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    q = n + k - 1;
    input.resize(q);
    bool sub2 = true;
    bool sub3 = true;
    for(int i = 0; i < q; i ++) {
        char t;
        cin >> t;
        if(t == 'C') {
            int a;
            cin >> a;
            input[i] = {'C',{a}};
        } else if(t == 'S') {
            int a,b;
            cin >> a >> b;
            if(a != 1 && b != 1) {
                sub2 = false;
            }
            if(abs(a-b) != 1) {
                sub3 = false;
            }
            nei[a].push_back(b);
            nei[b].push_back(a);
            input[i] = {t,{a,b}};
        } else {
            int a, b;
            cin >> a >> b;
            input[i] = {t,{a,b}};
        }
    }
    solveG();
    return 0;
    if(n <= 4000) {
        solve1();
    } else if(sub2) {
        solve2();
    } else {
        solveG();
    }
    return 0;
}

/*
3 18
Q 1 2
Q 2 1
Q 1 3
Q 3 1
Q 2 3
Q 3 2
S 1 3
Q 1 2
Q 2 1
Q 1 3
Q 3 1
Q 2 3
Q 3 2
S 1 2
Q 1 3
Q 3 1
Q 1 2
Q 2 1
Q 2 3
Q 3 2
*/

/*
4
Q 1 2
Q 2 1
Q 1 3
Q 3 1
Q 1 4
Q 4 1
Q 2 3
Q 3 2
Q 2 4
Q 4 2
Q 3 4
Q 4 3
*/

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:276:10: warning: variable 'sub3' set but not used [-Wunused-but-set-variable]
  276 |     bool sub3 = true;
      |          ^~~~
servers.cpp: In function 'void solve1()':
servers.cpp:225:25: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  225 |         int a = Q.s[0], b;
      |                         ^
servers.cpp: In function 'void solve2()':
servers.cpp:87:26: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |         if(date[a]*date[d] == 0) { return false; }
      |                    ~~~~~~^
servers.cpp:241:25: note: 'b' was declared here
  241 |         int a = Q.s[0], b;
      |                         ^
servers.cpp: In function 'void solveG()':
servers.cpp:194:9: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  194 |         if(sup[a][0] == d) { return date[a]; }
      |         ^~
servers.cpp:257:25: note: 'b' was declared here
  257 |         int a = Q.s[0], b;
      |                         ^

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 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