oj.uz

Submission #425828

# Submission time Handle Problem Language Result Execution time Memory
425828 2021-06-13T11:45:14 Z duality Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 38540 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int a[240000],b[240000];
vpii adjList[120000];
int parent[120000][17],good[120000][17],pe[120000],depth[120000];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (v != p) pe[v] = adjList[u][i].second,doDFS(v,u,d+1);
    }
    return 0;
}
int logn;
vpii edges;
int num[120000];
vi vv;
int lca(int u,int v) {
    int i;
    if (depth[u] < depth[v]) swap(u,v);
    for (i = logn-1; i >= 0; i--) {
        if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
    }
    if (u == v) return u;
    for (i = logn-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
    }
    return parent[u][0];
}
int path(int u,int v,int c) {
    if (u == v) return 1;
    int i,l = lca(u,v);
    if (l == u) {
        if (pe[v] > c) return 0;
        for (i = logn-1; i >= 0; i--) {
            if ((parent[v][i] != -1) && (depth[parent[v][i]] > depth[l])) {
                if (good[v][i] != -1) return 0;
                else v = parent[v][i];
            }
        }
        return 1;
    }
    else if (l == v) {
        for (i = logn-1; i >= 0; i--) {
            if ((parent[u][i] != -1) && (depth[parent[u][i]] > depth[l])) {
                if (good[u][i] != 1) return 0;
                else u = parent[u][i];
            }
        }
        if (pe[u] > c) return 0;
        return 1;
    }
    else {
        if (pe[v] > c) return 0;
        for (i = logn-1; i >= 0; i--) {
            if ((parent[u][i] != -1) && (depth[parent[u][i]] > depth[l])) {
                if (good[u][i] != 1) return 0;
                else u = parent[u][i];
            }
        }
        for (i = logn-1; i >= 0; i--) {
            if ((parent[v][i] != -1) && (depth[parent[v][i]] > depth[l])) {
                if (good[v][i] != -1) return 0;
                else v = parent[v][i];
            }
        }
        return pe[u] < pe[v];
    }
}
int main() {
    int i;
    int N,K;
    char c;
    scanf("%d %d",&N,&K);
    for (i = 0; i < N+K-1; i++) {
        scanf(" %c",&c);
        if (c == 'S') {
            scanf("%d %d",&a[i],&b[i]);
            a[i]--,b[i]--;
            adjList[a[i]].pb(mp(b[i],i));
            adjList[b[i]].pb(mp(a[i],i));
        }
        else if (c == 'Q') {
            scanf("%d %d",&a[i],&b[i]);
            a[i]--,b[i] *= -1;
        }
        else scanf("%d",&b[i]),a[i] = -1,b[i]--;
    }

    int j,k;
    doDFS(0,-1,0);
    for (i = 0; i < N; i++) {
        if ((parent[i][0] != -1) && (parent[parent[i][0]][0] != -1)) good[i][0] = (pe[i] < pe[parent[i][0]]) ? 1:-1;
        else good[i][0] = 0;
    }
    for (i = 1; (1 << i) < N; i++) {
        for (j = 0; j < N; j++) {
            if (parent[j][i-1] != -1) {
                parent[j][i] = parent[parent[j][i-1]][i-1];
                good[j][i] = (good[j][i-1] == good[parent[j][i-1]][i-1]) ? good[j][i-1]:0;
            }
            else parent[j][i] = -1;
        }
    }
    logn = i;
    int B = sqrt(N+K-1);
    for (i = 0; i < N+K-1; i += B) {
        int e = min(N+K-1,i+B);
        fill(num,num+N,1);
        for (j = i; j < e; j++) {
            if ((a[j] >= 0) && (b[j] >= 0)) num[a[j]] = num[b[j]] = 0;
        }
        for (j = 0; j < N; j++) {
            if (num[j] == 0) vv.pb(j);
        }
        for (j = (int) edges.size()-1; j >= 0; j--) num[edges[j].first] = num[edges[j].second] = num[edges[j].first]+num[edges[j].second];
        for (j = i; j < e; j++) {
            if ((a[j] >= 0) && (b[j] >= 0)) edges.pb(mp(a[j],b[j]));
            else if (a[j] == -1) {
                int ans = num[b[j]];
                for (k = 0; k < vv.size(); k++) {
                    if (path(b[j],vv[k],j)) ans++;
                }
                printf("%d\n",ans);
            }
            else printf(path(-b[j]-1,a[j],j) ? "yes\n":"no\n");
        }
        vv.clear();
    }

    return 0;
}

Compilation message

servers.cpp: In function 'int doDFS(int, int, int)':
servers.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         else scanf("%d",&b[i]),a[i] = -1,b[i]--;
      |              ~~~~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5296 KB Output is correct
2 Correct 75 ms 6584 KB Output is correct
3 Correct 92 ms 6684 KB Output is correct
4 Correct 83 ms 6708 KB Output is correct
5 Correct 99 ms 6800 KB Output is correct
6 Correct 75 ms 6720 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5296 KB Output is correct
2 Correct 75 ms 6584 KB Output is correct
3 Correct 92 ms 6684 KB Output is correct
4 Correct 83 ms 6708 KB Output is correct
5 Correct 99 ms 6800 KB Output is correct
6 Correct 75 ms 6720 KB Output is correct
7 Correct 51 ms 5296 KB Output is correct
8 Correct 211 ms 6296 KB Output is correct
9 Correct 122 ms 6400 KB Output is correct
10 Correct 291 ms 6300 KB Output is correct
11 Correct 135 ms 6464 KB Output is correct
12 Correct 105 ms 6612 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5316 KB Output is correct
2 Correct 638 ms 31632 KB Output is correct
3 Correct 634 ms 31596 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5316 KB Output is correct
2 Correct 638 ms 31632 KB Output is correct
3 Correct 634 ms 31596 KB Output is correct
4 Correct 45 ms 5284 KB Output is correct
5 Correct 1321 ms 31568 KB Output is correct
6 Correct 1982 ms 30552 KB Output is correct
7 Correct 2720 ms 30812 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5264 KB Output is correct
2 Correct 667 ms 38372 KB Output is correct
3 Correct 680 ms 38388 KB Output is correct
4 Correct 658 ms 38328 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5264 KB Output is correct
2 Correct 667 ms 38372 KB Output is correct
3 Correct 680 ms 38388 KB Output is correct
4 Correct 658 ms 38328 KB Output is correct
5 Correct 49 ms 5248 KB Output is correct
6 Execution timed out 3515 ms 37332 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5244 KB Output is correct
2 Correct 687 ms 31772 KB Output is correct
3 Correct 689 ms 32260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5244 KB Output is correct
2 Correct 687 ms 31772 KB Output is correct
3 Correct 689 ms 32260 KB Output is correct
4 Correct 51 ms 5240 KB Output is correct
5 Correct 2314 ms 31408 KB Output is correct
6 Correct 3045 ms 31804 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5316 KB Output is correct
2 Correct 643 ms 38404 KB Output is correct
3 Correct 736 ms 38408 KB Output is correct
4 Correct 707 ms 38448 KB Output is correct
5 Correct 49 ms 5316 KB Output is correct
6 Correct 684 ms 31752 KB Output is correct
7 Correct 697 ms 32228 KB Output is correct
8 Correct 854 ms 32724 KB Output is correct
9 Correct 692 ms 32628 KB Output is correct
10 Correct 735 ms 36480 KB Output is correct
11 Correct 877 ms 35988 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5316 KB Output is correct
2 Correct 643 ms 38404 KB Output is correct
3 Correct 736 ms 38408 KB Output is correct
4 Correct 707 ms 38448 KB Output is correct
5 Correct 49 ms 5316 KB Output is correct
6 Correct 684 ms 31752 KB Output is correct
7 Correct 697 ms 32228 KB Output is correct
8 Correct 854 ms 32724 KB Output is correct
9 Correct 692 ms 32628 KB Output is correct
10 Correct 735 ms 36480 KB Output is correct
11 Correct 877 ms 35988 KB Output is correct
12 Correct 52 ms 5244 KB Output is correct
13 Execution timed out 3578 ms 37324 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5280 KB Output is correct
2 Correct 88 ms 6652 KB Output is correct
3 Correct 77 ms 6688 KB Output is correct
4 Correct 83 ms 6684 KB Output is correct
5 Correct 84 ms 6804 KB Output is correct
6 Correct 70 ms 6592 KB Output is correct
7 Correct 44 ms 5260 KB Output is correct
8 Correct 607 ms 31684 KB Output is correct
9 Correct 596 ms 31672 KB Output is correct
10 Correct 46 ms 5316 KB Output is correct
11 Correct 648 ms 38540 KB Output is correct
12 Correct 668 ms 38428 KB Output is correct
13 Correct 651 ms 38312 KB Output is correct
14 Correct 55 ms 5316 KB Output is correct
15 Correct 673 ms 31736 KB Output is correct
16 Correct 666 ms 32204 KB Output is correct
17 Correct 822 ms 32668 KB Output is correct
18 Correct 671 ms 32664 KB Output is correct
19 Correct 742 ms 36660 KB Output is correct
20 Correct 928 ms 36040 KB Output is correct
21 Correct 613 ms 31924 KB Output is correct
22 Correct 625 ms 31988 KB Output is correct
23 Correct 692 ms 32280 KB Output is correct
24 Correct 627 ms 32296 KB Output is correct
25 Correct 780 ms 33496 KB Output is correct
26 Correct 706 ms 31724 KB Output is correct
27 Correct 732 ms 31764 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5280 KB Output is correct
2 Correct 88 ms 6652 KB Output is correct
3 Correct 77 ms 6688 KB Output is correct
4 Correct 83 ms 6684 KB Output is correct
5 Correct 84 ms 6804 KB Output is correct
6 Correct 70 ms 6592 KB Output is correct
7 Correct 44 ms 5260 KB Output is correct
8 Correct 607 ms 31684 KB Output is correct
9 Correct 596 ms 31672 KB Output is correct
10 Correct 46 ms 5316 KB Output is correct
11 Correct 648 ms 38540 KB Output is correct
12 Correct 668 ms 38428 KB Output is correct
13 Correct 651 ms 38312 KB Output is correct
14 Correct 55 ms 5316 KB Output is correct
15 Correct 673 ms 31736 KB Output is correct
16 Correct 666 ms 32204 KB Output is correct
17 Correct 822 ms 32668 KB Output is correct
18 Correct 671 ms 32664 KB Output is correct
19 Correct 742 ms 36660 KB Output is correct
20 Correct 928 ms 36040 KB Output is correct
21 Correct 613 ms 31924 KB Output is correct
22 Correct 625 ms 31988 KB Output is correct
23 Correct 692 ms 32280 KB Output is correct
24 Correct 627 ms 32296 KB Output is correct
25 Correct 780 ms 33496 KB Output is correct
26 Correct 706 ms 31724 KB Output is correct
27 Correct 732 ms 31764 KB Output is correct
28 Correct 49 ms 5232 KB Output is correct
29 Correct 204 ms 6260 KB Output is correct
30 Correct 113 ms 6368 KB Output is correct
31 Correct 301 ms 6368 KB Output is correct
32 Correct 150 ms 6540 KB Output is correct
33 Correct 120 ms 6364 KB Output is correct
34 Correct 43 ms 5316 KB Output is correct
35 Correct 1135 ms 31544 KB Output is correct
36 Correct 2013 ms 30616 KB Output is correct
37 Correct 2580 ms 30792 KB Output is correct
38 Correct 46 ms 5312 KB Output is correct
39 Execution timed out 3541 ms 37472 KB Time limit exceeded
40 Halted 0 ms 0 KB -