oj.uz

Submission #425846

# Submission time Handle Problem Language Result Execution time Memory
425846 2021-06-13T11:56:07 Z duality Inside information (BOI21_servers) C++11
62.5 / 100
 3500 ms 49388 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],sum[120000];
int disc[120000],fin[120000],num2 = 0;
vi order,child[120000];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d,disc[u] = num2++,order.pb(u);
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (v != p) child[u].pb(v),pe[v] = adjList[u][i].second,doDFS(v,u,d+1);
    }
    fin[u] = num2;
    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 getChild(int u,int v) {
    int l = 0,r = child[u].size()-1;
    while (l < r) {
        int m = (l+r+1) / 2;
        if (disc[child[u][m]] <= disc[v]) l = m;
        else r = m-1;
    }
    return child[u][l];
}
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;
        if (sum[v]-sum[getChild(l,v)] != -(depth[v]-depth[l]-1)) return 0;
        return 1;
    }
    else if (l == v) {
        int x = getChild(l,u);
        if (sum[u]-sum[x] != depth[u]-depth[l]-1) return 0;
        if (pe[x] > c) return 0;
        return 1;
    }
    else {
        if (pe[v] > c) return 0;
        int y = getChild(l,v);
        if (sum[v]-sum[y] != -(depth[v]-depth[l]-1)) return 0;
        int x = getChild(l,u);
        if (sum[u]-sum[x] != depth[u]-depth[l]-1) return 0;
        return pe[x] < pe[y];
    }
}
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; i < N; i++) {
        int u = order[i];
        sum[u] = good[u][0]+sum[parent[u][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:18: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]
   18 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int path(int, int, int)':
servers.cpp:52:9: warning: unused variable 'i' [-Wunused-variable]
   52 |     int i,l = lca(u,v);
      |         ^
servers.cpp: In function 'int main()':
servers.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:90:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         else scanf("%d",&b[i]),a[i] = -1,b[i]--;
      |              ~~~~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7240 KB Output is correct
2 Correct 112 ms 8216 KB Output is correct
3 Correct 94 ms 8252 KB Output is correct
4 Correct 86 ms 8244 KB Output is correct
5 Correct 82 ms 8620 KB Output is correct
6 Correct 98 ms 8132 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7240 KB Output is correct
2 Correct 112 ms 8216 KB Output is correct
3 Correct 94 ms 8252 KB Output is correct
4 Correct 86 ms 8244 KB Output is correct
5 Correct 82 ms 8620 KB Output is correct
6 Correct 98 ms 8132 KB Output is correct
7 Correct 64 ms 7252 KB Output is correct
8 Correct 296 ms 8108 KB Output is correct
9 Correct 134 ms 8212 KB Output is correct
10 Correct 323 ms 8240 KB Output is correct
11 Correct 139 ms 8516 KB Output is correct
12 Correct 149 ms 8312 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7260 KB Output is correct
2 Correct 693 ms 34856 KB Output is correct
3 Correct 662 ms 34652 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7260 KB Output is correct
2 Correct 693 ms 34856 KB Output is correct
3 Correct 662 ms 34652 KB Output is correct
4 Correct 48 ms 7232 KB Output is correct
5 Correct 1597 ms 34700 KB Output is correct
6 Correct 3372 ms 35100 KB Output is correct
7 Execution timed out 3539 ms 34716 KB Time limit exceeded

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7260 KB Output is correct
2 Correct 656 ms 49388 KB Output is correct
3 Correct 678 ms 49168 KB Output is correct
4 Correct 687 ms 49176 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7260 KB Output is correct
2 Correct 656 ms 49388 KB Output is correct
3 Correct 678 ms 49168 KB Output is correct
4 Correct 687 ms 49176 KB Output is correct
5 Correct 48 ms 7268 KB Output is correct
6 Execution timed out 3560 ms 48760 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7192 KB Output is correct
2 Correct 687 ms 35008 KB Output is correct
3 Correct 714 ms 35356 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7192 KB Output is correct
2 Correct 687 ms 35008 KB Output is correct
3 Correct 714 ms 35356 KB Output is correct
4 Correct 47 ms 7244 KB Output is correct
5 Correct 1997 ms 35204 KB Output is correct
6 Correct 2862 ms 35332 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7260 KB Output is correct
2 Correct 699 ms 49292 KB Output is correct
3 Correct 670 ms 49224 KB Output is correct
4 Correct 664 ms 49320 KB Output is correct
5 Correct 55 ms 7232 KB Output is correct
6 Correct 689 ms 35196 KB Output is correct
7 Correct 710 ms 35256 KB Output is correct
8 Correct 817 ms 35024 KB Output is correct
9 Correct 688 ms 34976 KB Output is correct
10 Correct 737 ms 40040 KB Output is correct
11 Correct 942 ms 39056 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7260 KB Output is correct
2 Correct 699 ms 49292 KB Output is correct
3 Correct 670 ms 49224 KB Output is correct
4 Correct 664 ms 49320 KB Output is correct
5 Correct 55 ms 7232 KB Output is correct
6 Correct 689 ms 35196 KB Output is correct
7 Correct 710 ms 35256 KB Output is correct
8 Correct 817 ms 35024 KB Output is correct
9 Correct 688 ms 34976 KB Output is correct
10 Correct 737 ms 40040 KB Output is correct
11 Correct 942 ms 39056 KB Output is correct
12 Correct 46 ms 7200 KB Output is correct
13 Execution timed out 3568 ms 48712 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7256 KB Output is correct
2 Correct 73 ms 8212 KB Output is correct
3 Correct 87 ms 8192 KB Output is correct
4 Correct 91 ms 8304 KB Output is correct
5 Correct 88 ms 8648 KB Output is correct
6 Correct 104 ms 8180 KB Output is correct
7 Correct 49 ms 7236 KB Output is correct
8 Correct 685 ms 34756 KB Output is correct
9 Correct 685 ms 34688 KB Output is correct
10 Correct 47 ms 7236 KB Output is correct
11 Correct 687 ms 49316 KB Output is correct
12 Correct 690 ms 49164 KB Output is correct
13 Correct 670 ms 49212 KB Output is correct
14 Correct 49 ms 7240 KB Output is correct
15 Correct 668 ms 35068 KB Output is correct
16 Correct 712 ms 35140 KB Output is correct
17 Correct 834 ms 35004 KB Output is correct
18 Correct 715 ms 35020 KB Output is correct
19 Correct 812 ms 40000 KB Output is correct
20 Correct 917 ms 39004 KB Output is correct
21 Correct 710 ms 34224 KB Output is correct
22 Correct 696 ms 34464 KB Output is correct
23 Correct 678 ms 34436 KB Output is correct
24 Correct 689 ms 34436 KB Output is correct
25 Correct 731 ms 38644 KB Output is correct
26 Correct 779 ms 34920 KB Output is correct
27 Correct 806 ms 34948 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7256 KB Output is correct
2 Correct 73 ms 8212 KB Output is correct
3 Correct 87 ms 8192 KB Output is correct
4 Correct 91 ms 8304 KB Output is correct
5 Correct 88 ms 8648 KB Output is correct
6 Correct 104 ms 8180 KB Output is correct
7 Correct 49 ms 7236 KB Output is correct
8 Correct 685 ms 34756 KB Output is correct
9 Correct 685 ms 34688 KB Output is correct
10 Correct 47 ms 7236 KB Output is correct
11 Correct 687 ms 49316 KB Output is correct
12 Correct 690 ms 49164 KB Output is correct
13 Correct 670 ms 49212 KB Output is correct
14 Correct 49 ms 7240 KB Output is correct
15 Correct 668 ms 35068 KB Output is correct
16 Correct 712 ms 35140 KB Output is correct
17 Correct 834 ms 35004 KB Output is correct
18 Correct 715 ms 35020 KB Output is correct
19 Correct 812 ms 40000 KB Output is correct
20 Correct 917 ms 39004 KB Output is correct
21 Correct 710 ms 34224 KB Output is correct
22 Correct 696 ms 34464 KB Output is correct
23 Correct 678 ms 34436 KB Output is correct
24 Correct 689 ms 34436 KB Output is correct
25 Correct 731 ms 38644 KB Output is correct
26 Correct 779 ms 34920 KB Output is correct
27 Correct 806 ms 34948 KB Output is correct
28 Correct 47 ms 7260 KB Output is correct
29 Correct 206 ms 8052 KB Output is correct
30 Correct 127 ms 8240 KB Output is correct
31 Correct 288 ms 8280 KB Output is correct
32 Correct 133 ms 8580 KB Output is correct
33 Correct 149 ms 8216 KB Output is correct
34 Correct 49 ms 7200 KB Output is correct
35 Correct 1578 ms 34852 KB Output is correct
36 Correct 3410 ms 35000 KB Output is correct
37 Execution timed out 3536 ms 34564 KB Time limit exceeded
38 Halted 0 ms 0 KB -