oj.uz

Submission #554172

# Submission time Handle Problem Language Result Execution time Memory
554172 2022-04-27T18:32:04 Z alontanay Inside information (BOI21_servers) C++14
20 / 100
 215 ms 41940 KB 
#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[mxN];
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";
        }
    }
}

int LL[mxN];
int RR[mxN];
void solve3() {
    SOLG solG;
    for(int i = 1 ; i<= n; i ++) {
        LL[i] = RR[i] = i;
        cnt[i] = 1;
    }
    segDn.update(1,1);
    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);
            int nl = min(LL[a],LL[b]);
            int nr = max(RR[a],RR[b]);
            LL[a] = LL[b] = nl;
            RR[a] = RR[b] = nr;
            segDn.update(nl,1);
            segDn.update(nr+1,-1);
        } else if(t == 'Q') {
            cout << (solG.Query(a,b) ? "yes\n" : "no\n");
        } else {
            cout << segDn.query(0,a+1) << "\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}};
        }
    }
    if(n <= 4000) {
        solve1();
    } else if(sub2) {
        solve2();
    } else if(sub3) {
        solve3();
    } 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
*/

/*
3 9
C 1
C 2
C 3
S 1 2
C 1
C 2
C 3
S 2 3
C 1
C 2
C 3
*/

Compilation message

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:292:32: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  292 |             cout << (solG.Query(a,b) ? "yes\n" : "no\n");
      |                      ~~~~~~~~~~^~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29412 KB Output is correct
2 Correct 66 ms 29908 KB Output is correct
3 Correct 82 ms 29928 KB Output is correct
4 Correct 80 ms 29796 KB Output is correct
5 Correct 62 ms 29872 KB Output is correct
6 Correct 101 ms 29888 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29412 KB Output is correct
2 Correct 66 ms 29908 KB Output is correct
3 Correct 82 ms 29928 KB Output is correct
4 Correct 80 ms 29796 KB Output is correct
5 Correct 62 ms 29872 KB Output is correct
6 Correct 101 ms 29888 KB Output is correct
7 Correct 36 ms 29388 KB Output is correct
8 Correct 63 ms 29584 KB Output is correct
9 Correct 67 ms 29748 KB Output is correct
10 Correct 57 ms 29648 KB Output is correct
11 Correct 59 ms 29644 KB Output is correct
12 Correct 97 ms 29832 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 29452 KB Output is correct
2 Correct 86 ms 26480 KB Output is correct
3 Correct 83 ms 26604 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 29452 KB Output is correct
2 Correct 86 ms 26480 KB Output is correct
3 Correct 83 ms 26604 KB Output is correct
4 Correct 36 ms 29476 KB Output is correct
5 Correct 85 ms 28360 KB Output is correct
6 Correct 88 ms 27592 KB Output is correct
7 Correct 83 ms 27716 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 29464 KB Output is correct
2 Incorrect 211 ms 41656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 29464 KB Output is correct
2 Incorrect 211 ms 41656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29460 KB Output is correct
2 Correct 164 ms 35864 KB Output is correct
3 Correct 193 ms 36048 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29460 KB Output is correct
2 Correct 164 ms 35864 KB Output is correct
3 Correct 193 ms 36048 KB Output is correct
4 Correct 37 ms 29388 KB Output is correct
5 Incorrect 141 ms 37676 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29468 KB Output is correct
2 Incorrect 209 ms 41940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29468 KB Output is correct
2 Incorrect 209 ms 41940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29516 KB Output is correct
2 Correct 65 ms 29748 KB Output is correct
3 Correct 65 ms 29908 KB Output is correct
4 Correct 66 ms 29832 KB Output is correct
5 Correct 65 ms 29772 KB Output is correct
6 Correct 102 ms 29920 KB Output is correct
7 Correct 36 ms 29480 KB Output is correct
8 Correct 92 ms 26460 KB Output is correct
9 Correct 85 ms 26668 KB Output is correct
10 Correct 35 ms 29388 KB Output is correct
11 Incorrect 215 ms 41808 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29516 KB Output is correct
2 Correct 65 ms 29748 KB Output is correct
3 Correct 65 ms 29908 KB Output is correct
4 Correct 66 ms 29832 KB Output is correct
5 Correct 65 ms 29772 KB Output is correct
6 Correct 102 ms 29920 KB Output is correct
7 Correct 36 ms 29480 KB Output is correct
8 Correct 92 ms 26460 KB Output is correct
9 Correct 85 ms 26668 KB Output is correct
10 Correct 35 ms 29388 KB Output is correct
11 Incorrect 215 ms 41808 KB Output isn't correct
12 Halted 0 ms 0 KB -