oj.uz

답안 #554148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554148 2022-04-27T17:33:52 Z alontanay Inside information (BOI21_servers) C++14
55 / 100
 250 ms 42380 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}};
        }
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28688 KB Output is correct
2 Correct 71 ms 29228 KB Output is correct
3 Correct 71 ms 29164 KB Output is correct
4 Correct 69 ms 28992 KB Output is correct
5 Correct 70 ms 29000 KB Output is correct
6 Correct 89 ms 29132 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28688 KB Output is correct
2 Correct 71 ms 29228 KB Output is correct
3 Correct 71 ms 29164 KB Output is correct
4 Correct 69 ms 28992 KB Output is correct
5 Correct 70 ms 29000 KB Output is correct
6 Correct 89 ms 29132 KB Output is correct
7 Correct 38 ms 28620 KB Output is correct
8 Correct 70 ms 29960 KB Output is correct
9 Correct 73 ms 30108 KB Output is correct
10 Correct 65 ms 29992 KB Output is correct
11 Correct 66 ms 29908 KB Output is correct
12 Correct 85 ms 30188 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 28700 KB Output is correct
2 Correct 85 ms 25764 KB Output is correct
3 Correct 88 ms 25796 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 28700 KB Output is correct
2 Correct 85 ms 25764 KB Output is correct
3 Correct 88 ms 25796 KB Output is correct
4 Correct 36 ms 28772 KB Output is correct
5 Correct 89 ms 28276 KB Output is correct
6 Correct 88 ms 27608 KB Output is correct
7 Correct 84 ms 27736 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 28612 KB Output is correct
2 Correct 181 ms 39508 KB Output is correct
3 Correct 208 ms 39684 KB Output is correct
4 Correct 157 ms 39664 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 28612 KB Output is correct
2 Correct 181 ms 39508 KB Output is correct
3 Correct 208 ms 39684 KB Output is correct
4 Correct 157 ms 39664 KB Output is correct
5 Correct 38 ms 28652 KB Output is correct
6 Incorrect 176 ms 42348 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28696 KB Output is correct
2 Correct 175 ms 35044 KB Output is correct
3 Correct 203 ms 35316 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28696 KB Output is correct
2 Correct 175 ms 35044 KB Output is correct
3 Correct 203 ms 35316 KB Output is correct
4 Correct 42 ms 28700 KB Output is correct
5 Incorrect 134 ms 37828 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28628 KB Output is correct
2 Correct 184 ms 39452 KB Output is correct
3 Correct 189 ms 39604 KB Output is correct
4 Correct 174 ms 39576 KB Output is correct
5 Correct 37 ms 28764 KB Output is correct
6 Correct 163 ms 35260 KB Output is correct
7 Correct 191 ms 35232 KB Output is correct
8 Correct 231 ms 35660 KB Output is correct
9 Correct 206 ms 35740 KB Output is correct
10 Correct 188 ms 36896 KB Output is correct
11 Correct 245 ms 36572 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 28628 KB Output is correct
2 Correct 184 ms 39452 KB Output is correct
3 Correct 189 ms 39604 KB Output is correct
4 Correct 174 ms 39576 KB Output is correct
5 Correct 37 ms 28764 KB Output is correct
6 Correct 163 ms 35260 KB Output is correct
7 Correct 191 ms 35232 KB Output is correct
8 Correct 231 ms 35660 KB Output is correct
9 Correct 206 ms 35740 KB Output is correct
10 Correct 188 ms 36896 KB Output is correct
11 Correct 245 ms 36572 KB Output is correct
12 Correct 37 ms 28792 KB Output is correct
13 Incorrect 185 ms 42380 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 28732 KB Output is correct
2 Correct 68 ms 29056 KB Output is correct
3 Correct 69 ms 29236 KB Output is correct
4 Correct 68 ms 29024 KB Output is correct
5 Correct 79 ms 29004 KB Output is correct
6 Correct 88 ms 29172 KB Output is correct
7 Correct 38 ms 28656 KB Output is correct
8 Correct 95 ms 25724 KB Output is correct
9 Correct 82 ms 25804 KB Output is correct
10 Correct 40 ms 28840 KB Output is correct
11 Correct 181 ms 39644 KB Output is correct
12 Correct 183 ms 39596 KB Output is correct
13 Correct 156 ms 39628 KB Output is correct
14 Correct 38 ms 28796 KB Output is correct
15 Correct 166 ms 35248 KB Output is correct
16 Correct 178 ms 35260 KB Output is correct
17 Correct 236 ms 35652 KB Output is correct
18 Correct 205 ms 35788 KB Output is correct
19 Correct 184 ms 36940 KB Output is correct
20 Correct 250 ms 36648 KB Output is correct
21 Correct 186 ms 35824 KB Output is correct
22 Correct 191 ms 35776 KB Output is correct
23 Correct 212 ms 35952 KB Output is correct
24 Correct 196 ms 35928 KB Output is correct
25 Correct 200 ms 36676 KB Output is correct
26 Correct 177 ms 35444 KB Output is correct
27 Correct 143 ms 35532 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 28732 KB Output is correct
2 Correct 68 ms 29056 KB Output is correct
3 Correct 69 ms 29236 KB Output is correct
4 Correct 68 ms 29024 KB Output is correct
5 Correct 79 ms 29004 KB Output is correct
6 Correct 88 ms 29172 KB Output is correct
7 Correct 38 ms 28656 KB Output is correct
8 Correct 95 ms 25724 KB Output is correct
9 Correct 82 ms 25804 KB Output is correct
10 Correct 40 ms 28840 KB Output is correct
11 Correct 181 ms 39644 KB Output is correct
12 Correct 183 ms 39596 KB Output is correct
13 Correct 156 ms 39628 KB Output is correct
14 Correct 38 ms 28796 KB Output is correct
15 Correct 166 ms 35248 KB Output is correct
16 Correct 178 ms 35260 KB Output is correct
17 Correct 236 ms 35652 KB Output is correct
18 Correct 205 ms 35788 KB Output is correct
19 Correct 184 ms 36940 KB Output is correct
20 Correct 250 ms 36648 KB Output is correct
21 Correct 186 ms 35824 KB Output is correct
22 Correct 191 ms 35776 KB Output is correct
23 Correct 212 ms 35952 KB Output is correct
24 Correct 196 ms 35928 KB Output is correct
25 Correct 200 ms 36676 KB Output is correct
26 Correct 177 ms 35444 KB Output is correct
27 Correct 143 ms 35532 KB Output is correct
28 Correct 40 ms 28704 KB Output is correct
29 Correct 66 ms 30016 KB Output is correct
30 Correct 72 ms 30080 KB Output is correct
31 Correct 67 ms 29992 KB Output is correct
32 Correct 64 ms 29996 KB Output is correct
33 Correct 89 ms 30212 KB Output is correct
34 Correct 38 ms 29516 KB Output is correct
35 Correct 87 ms 28356 KB Output is correct
36 Correct 79 ms 27624 KB Output is correct
37 Correct 81 ms 27704 KB Output is correct
38 Correct 38 ms 29396 KB Output is correct
39 Incorrect 182 ms 42232 KB Extra information in the output file
40 Halted 0 ms 0 KB -