oj.uz

Submission #554143

# Submission time Handle Problem Language Result Execution time Memory
554143 2022-04-27T17:32:34 Z alontanay Inside information (BOI21_servers) C++14
50 / 100
 258 ms 42756 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[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

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

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13772 KB Output is correct
2 Correct 80 ms 14952 KB Output is correct
3 Correct 77 ms 15004 KB Output is correct
4 Correct 90 ms 15052 KB Output is correct
5 Correct 71 ms 15164 KB Output is correct
6 Correct 79 ms 15016 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13772 KB Output is correct
2 Correct 80 ms 14952 KB Output is correct
3 Correct 77 ms 15004 KB Output is correct
4 Correct 90 ms 15052 KB Output is correct
5 Correct 71 ms 15164 KB Output is correct
6 Correct 79 ms 15016 KB Output is correct
7 Incorrect 49 ms 13772 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13772 KB Output is correct
2 Correct 182 ms 37800 KB Output is correct
3 Correct 180 ms 37864 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13772 KB Output is correct
2 Correct 182 ms 37800 KB Output is correct
3 Correct 180 ms 37864 KB Output is correct
4 Incorrect 46 ms 13728 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13724 KB Output is correct
2 Correct 200 ms 42756 KB Output is correct
3 Correct 188 ms 42740 KB Output is correct
4 Correct 161 ms 42584 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13724 KB Output is correct
2 Correct 200 ms 42756 KB Output is correct
3 Correct 188 ms 42740 KB Output is correct
4 Correct 161 ms 42584 KB Output is correct
5 Incorrect 43 ms 13772 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13816 KB Output is correct
2 Correct 176 ms 38240 KB Output is correct
3 Correct 199 ms 38260 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13816 KB Output is correct
2 Correct 176 ms 38240 KB Output is correct
3 Correct 199 ms 38260 KB Output is correct
4 Incorrect 47 ms 13772 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13800 KB Output is correct
2 Correct 206 ms 42700 KB Output is correct
3 Correct 207 ms 42720 KB Output is correct
4 Correct 164 ms 42608 KB Output is correct
5 Correct 49 ms 13800 KB Output is correct
6 Correct 166 ms 38212 KB Output is correct
7 Correct 188 ms 38220 KB Output is correct
8 Correct 231 ms 38712 KB Output is correct
9 Correct 213 ms 38732 KB Output is correct
10 Correct 184 ms 40108 KB Output is correct
11 Correct 249 ms 39644 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13800 KB Output is correct
2 Correct 206 ms 42700 KB Output is correct
3 Correct 207 ms 42720 KB Output is correct
4 Correct 164 ms 42608 KB Output is correct
5 Correct 49 ms 13800 KB Output is correct
6 Correct 166 ms 38212 KB Output is correct
7 Correct 188 ms 38220 KB Output is correct
8 Correct 231 ms 38712 KB Output is correct
9 Correct 213 ms 38732 KB Output is correct
10 Correct 184 ms 40108 KB Output is correct
11 Correct 249 ms 39644 KB Output is correct
12 Incorrect 44 ms 13704 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13756 KB Output is correct
2 Correct 81 ms 14960 KB Output is correct
3 Correct 73 ms 15064 KB Output is correct
4 Correct 93 ms 14968 KB Output is correct
5 Correct 72 ms 15144 KB Output is correct
6 Correct 83 ms 15036 KB Output is correct
7 Correct 46 ms 13760 KB Output is correct
8 Correct 180 ms 37772 KB Output is correct
9 Correct 178 ms 37800 KB Output is correct
10 Correct 43 ms 13772 KB Output is correct
11 Correct 191 ms 42752 KB Output is correct
12 Correct 198 ms 42676 KB Output is correct
13 Correct 170 ms 42632 KB Output is correct
14 Correct 53 ms 13772 KB Output is correct
15 Correct 174 ms 38288 KB Output is correct
16 Correct 200 ms 38316 KB Output is correct
17 Correct 258 ms 38676 KB Output is correct
18 Correct 231 ms 38748 KB Output is correct
19 Correct 188 ms 40024 KB Output is correct
20 Correct 257 ms 39656 KB Output is correct
21 Correct 194 ms 38836 KB Output is correct
22 Correct 199 ms 38876 KB Output is correct
23 Correct 203 ms 38868 KB Output is correct
24 Correct 210 ms 38956 KB Output is correct
25 Correct 203 ms 39800 KB Output is correct
26 Correct 161 ms 38592 KB Output is correct
27 Correct 145 ms 38612 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13756 KB Output is correct
2 Correct 81 ms 14960 KB Output is correct
3 Correct 73 ms 15064 KB Output is correct
4 Correct 93 ms 14968 KB Output is correct
5 Correct 72 ms 15144 KB Output is correct
6 Correct 83 ms 15036 KB Output is correct
7 Correct 46 ms 13760 KB Output is correct
8 Correct 180 ms 37772 KB Output is correct
9 Correct 178 ms 37800 KB Output is correct
10 Correct 43 ms 13772 KB Output is correct
11 Correct 191 ms 42752 KB Output is correct
12 Correct 198 ms 42676 KB Output is correct
13 Correct 170 ms 42632 KB Output is correct
14 Correct 53 ms 13772 KB Output is correct
15 Correct 174 ms 38288 KB Output is correct
16 Correct 200 ms 38316 KB Output is correct
17 Correct 258 ms 38676 KB Output is correct
18 Correct 231 ms 38748 KB Output is correct
19 Correct 188 ms 40024 KB Output is correct
20 Correct 257 ms 39656 KB Output is correct
21 Correct 194 ms 38836 KB Output is correct
22 Correct 199 ms 38876 KB Output is correct
23 Correct 203 ms 38868 KB Output is correct
24 Correct 210 ms 38956 KB Output is correct
25 Correct 203 ms 39800 KB Output is correct
26 Correct 161 ms 38592 KB Output is correct
27 Correct 145 ms 38612 KB Output is correct
28 Incorrect 50 ms 13756 KB Extra information in the output file
29 Halted 0 ms 0 KB -