oj.uz

Submission #425866

# Submission time Handle Problem Language Result Execution time Memory
425866 2021-06-13T12:06:08 Z duality Inside information (BOI21_servers) C++11
100 / 100
 2673 ms 84632 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],disc2[120000],num2 = 0,num3 = 0;
vi order,child[120000];
pii sparse[240000][18];
int logg[240001];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d,disc[u] = num2++,order.pb(u);
    disc2[u] = num3++,sparse[num3-1][0] = mp(d,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),sparse[num3++][0] = mp(d,u);
    }
    fin[u] = num2;
    return 0;
}
vpii edges;
int num[120000];
vi vv;
int lca(int u,int v) {
    u = disc2[u],v = disc2[v];
    if (u > v) swap(u,v);
    int l = logg[v-u+1];
    return min(sparse[u][l],sparse[v-(1 << l)+1][l]).second;
}
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 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) <= 2*N; i++) {
        for (j = 0; j <= 2*N-(1 << i); j++) sparse[j][i] = min(sparse[j][i-1],sparse[j+(1 << (i-1))][i-1]);
    }
    for (i = 2; i <= 2*N; i++) logg[i] = logg[i/2]+1;
    int B = 0.6*sqrt(N+K-1)+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:21: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]
   21 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:86:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         else scanf("%d",&b[i]),a[i] = -1,b[i]--;
      |              ~~~~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7236 KB Output is correct
2 Correct 74 ms 9396 KB Output is correct
3 Correct 91 ms 9388 KB Output is correct
4 Correct 73 ms 9444 KB Output is correct
5 Correct 81 ms 9872 KB Output is correct
6 Correct 105 ms 9328 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7236 KB Output is correct
2 Correct 74 ms 9396 KB Output is correct
3 Correct 91 ms 9388 KB Output is correct
4 Correct 73 ms 9444 KB Output is correct
5 Correct 81 ms 9872 KB Output is correct
6 Correct 105 ms 9328 KB Output is correct
7 Correct 44 ms 7236 KB Output is correct
8 Correct 106 ms 9300 KB Output is correct
9 Correct 112 ms 9428 KB Output is correct
10 Correct 111 ms 9372 KB Output is correct
11 Correct 99 ms 9796 KB Output is correct
12 Correct 131 ms 9472 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7280 KB Output is correct
2 Correct 1044 ms 69860 KB Output is correct
3 Correct 1068 ms 70064 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7280 KB Output is correct
2 Correct 1044 ms 69860 KB Output is correct
3 Correct 1068 ms 70064 KB Output is correct
4 Correct 60 ms 7548 KB Output is correct
5 Correct 1474 ms 69912 KB Output is correct
6 Correct 2170 ms 70192 KB Output is correct
7 Correct 2510 ms 70084 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7236 KB Output is correct
2 Correct 973 ms 84484 KB Output is correct
3 Correct 955 ms 84428 KB Output is correct
4 Correct 915 ms 84416 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7236 KB Output is correct
2 Correct 973 ms 84484 KB Output is correct
3 Correct 955 ms 84428 KB Output is correct
4 Correct 915 ms 84416 KB Output is correct
5 Correct 43 ms 7240 KB Output is correct
6 Correct 1718 ms 84520 KB Output is correct
7 Correct 1049 ms 84472 KB Output is correct
8 Correct 2187 ms 84360 KB Output is correct
9 Correct 2281 ms 84632 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7244 KB Output is correct
2 Correct 1020 ms 70420 KB Output is correct
3 Correct 1098 ms 70460 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7244 KB Output is correct
2 Correct 1020 ms 70420 KB Output is correct
3 Correct 1098 ms 70460 KB Output is correct
4 Correct 46 ms 7280 KB Output is correct
5 Correct 1339 ms 70396 KB Output is correct
6 Correct 1783 ms 70252 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7236 KB Output is correct
2 Correct 1000 ms 84416 KB Output is correct
3 Correct 970 ms 84404 KB Output is correct
4 Correct 909 ms 84360 KB Output is correct
5 Correct 63 ms 7184 KB Output is correct
6 Correct 992 ms 70300 KB Output is correct
7 Correct 1081 ms 70420 KB Output is correct
8 Correct 1221 ms 70200 KB Output is correct
9 Correct 1037 ms 70252 KB Output is correct
10 Correct 1045 ms 75124 KB Output is correct
11 Correct 1146 ms 74344 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7236 KB Output is correct
2 Correct 1000 ms 84416 KB Output is correct
3 Correct 970 ms 84404 KB Output is correct
4 Correct 909 ms 84360 KB Output is correct
5 Correct 63 ms 7184 KB Output is correct
6 Correct 992 ms 70300 KB Output is correct
7 Correct 1081 ms 70420 KB Output is correct
8 Correct 1221 ms 70200 KB Output is correct
9 Correct 1037 ms 70252 KB Output is correct
10 Correct 1045 ms 75124 KB Output is correct
11 Correct 1146 ms 74344 KB Output is correct
12 Correct 45 ms 7208 KB Output is correct
13 Correct 1718 ms 84524 KB Output is correct
14 Correct 1052 ms 84396 KB Output is correct
15 Correct 2253 ms 84272 KB Output is correct
16 Correct 2166 ms 84300 KB Output is correct
17 Correct 44 ms 7308 KB Output is correct
18 Correct 1258 ms 70332 KB Output is correct
19 Correct 1895 ms 70316 KB Output is correct
20 Correct 1487 ms 70144 KB Output is correct
21 Correct 2211 ms 70080 KB Output is correct
22 Correct 2202 ms 73976 KB Output is correct
23 Correct 1756 ms 75796 KB Output is correct
24 Correct 1238 ms 75676 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7236 KB Output is correct
2 Correct 75 ms 9348 KB Output is correct
3 Correct 96 ms 9372 KB Output is correct
4 Correct 79 ms 9448 KB Output is correct
5 Correct 79 ms 9796 KB Output is correct
6 Correct 107 ms 9436 KB Output is correct
7 Correct 62 ms 7236 KB Output is correct
8 Correct 1022 ms 70040 KB Output is correct
9 Correct 1074 ms 69980 KB Output is correct
10 Correct 43 ms 7236 KB Output is correct
11 Correct 973 ms 84388 KB Output is correct
12 Correct 936 ms 84516 KB Output is correct
13 Correct 918 ms 84428 KB Output is correct
14 Correct 47 ms 7284 KB Output is correct
15 Correct 1027 ms 70256 KB Output is correct
16 Correct 1083 ms 70336 KB Output is correct
17 Correct 1094 ms 70120 KB Output is correct
18 Correct 1038 ms 70160 KB Output is correct
19 Correct 1045 ms 75200 KB Output is correct
20 Correct 1151 ms 74276 KB Output is correct
21 Correct 1106 ms 69492 KB Output is correct
22 Correct 1063 ms 69660 KB Output is correct
23 Correct 1045 ms 69604 KB Output is correct
24 Correct 997 ms 69644 KB Output is correct
25 Correct 1046 ms 73832 KB Output is correct
26 Correct 1146 ms 70248 KB Output is correct
27 Correct 1171 ms 70228 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7236 KB Output is correct
2 Correct 75 ms 9348 KB Output is correct
3 Correct 96 ms 9372 KB Output is correct
4 Correct 79 ms 9448 KB Output is correct
5 Correct 79 ms 9796 KB Output is correct
6 Correct 107 ms 9436 KB Output is correct
7 Correct 62 ms 7236 KB Output is correct
8 Correct 1022 ms 70040 KB Output is correct
9 Correct 1074 ms 69980 KB Output is correct
10 Correct 43 ms 7236 KB Output is correct
11 Correct 973 ms 84388 KB Output is correct
12 Correct 936 ms 84516 KB Output is correct
13 Correct 918 ms 84428 KB Output is correct
14 Correct 47 ms 7284 KB Output is correct
15 Correct 1027 ms 70256 KB Output is correct
16 Correct 1083 ms 70336 KB Output is correct
17 Correct 1094 ms 70120 KB Output is correct
18 Correct 1038 ms 70160 KB Output is correct
19 Correct 1045 ms 75200 KB Output is correct
20 Correct 1151 ms 74276 KB Output is correct
21 Correct 1106 ms 69492 KB Output is correct
22 Correct 1063 ms 69660 KB Output is correct
23 Correct 1045 ms 69604 KB Output is correct
24 Correct 997 ms 69644 KB Output is correct
25 Correct 1046 ms 73832 KB Output is correct
26 Correct 1146 ms 70248 KB Output is correct
27 Correct 1171 ms 70228 KB Output is correct
28 Correct 46 ms 7260 KB Output is correct
29 Correct 104 ms 9344 KB Output is correct
30 Correct 108 ms 9452 KB Output is correct
31 Correct 99 ms 9468 KB Output is correct
32 Correct 81 ms 9724 KB Output is correct
33 Correct 121 ms 9460 KB Output is correct
34 Correct 50 ms 7236 KB Output is correct
35 Correct 1471 ms 70040 KB Output is correct
36 Correct 2160 ms 70356 KB Output is correct
37 Correct 2518 ms 70200 KB Output is correct
38 Correct 51 ms 7236 KB Output is correct
39 Correct 1660 ms 84500 KB Output is correct
40 Correct 1083 ms 84592 KB Output is correct
41 Correct 2133 ms 84268 KB Output is correct
42 Correct 2163 ms 84276 KB Output is correct
43 Correct 46 ms 7236 KB Output is correct
44 Correct 1297 ms 70348 KB Output is correct
45 Correct 1785 ms 70352 KB Output is correct
46 Correct 1470 ms 70292 KB Output is correct
47 Correct 2276 ms 70280 KB Output is correct
48 Correct 2268 ms 74080 KB Output is correct
49 Correct 1799 ms 75840 KB Output is correct
50 Correct 1255 ms 75504 KB Output is correct
51 Correct 2279 ms 69764 KB Output is correct
52 Correct 2673 ms 70156 KB Output is correct
53 Correct 2629 ms 72396 KB Output is correct
54 Correct 2297 ms 73104 KB Output is correct
55 Correct 2599 ms 72216 KB Output is correct
56 Correct 2021 ms 72572 KB Output is correct
57 Correct 2152 ms 76228 KB Output is correct
58 Correct 1834 ms 72840 KB Output is correct
59 Correct 1179 ms 73492 KB Output is correct