oj.uz

Submission #425860

# Submission time Handle Problem Language Result Execution time Memory
425860 2021-06-13T12:03:07 Z duality Inside information (BOI21_servers) C++11
82.5 / 100
 3500 ms 87464 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 = 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: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 46 ms 7216 KB Output is correct
2 Correct 68 ms 9304 KB Output is correct
3 Correct 83 ms 9364 KB Output is correct
4 Correct 68 ms 9560 KB Output is correct
5 Correct 70 ms 9836 KB Output is correct
6 Correct 102 ms 9392 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7216 KB Output is correct
2 Correct 68 ms 9304 KB Output is correct
3 Correct 83 ms 9364 KB Output is correct
4 Correct 68 ms 9560 KB Output is correct
5 Correct 70 ms 9836 KB Output is correct
6 Correct 102 ms 9392 KB Output is correct
7 Correct 44 ms 7260 KB Output is correct
8 Correct 118 ms 9324 KB Output is correct
9 Correct 123 ms 9448 KB Output is correct
10 Correct 113 ms 9532 KB Output is correct
11 Correct 79 ms 9788 KB Output is correct
12 Correct 136 ms 9456 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7236 KB Output is correct
2 Correct 739 ms 69876 KB Output is correct
3 Correct 784 ms 69932 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7236 KB Output is correct
2 Correct 739 ms 69876 KB Output is correct
3 Correct 784 ms 69932 KB Output is correct
4 Correct 62 ms 7212 KB Output is correct
5 Correct 1593 ms 69988 KB Output is correct
6 Correct 2824 ms 70232 KB Output is correct
7 Correct 3472 ms 70020 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7184 KB Output is correct
2 Correct 702 ms 84368 KB Output is correct
3 Correct 704 ms 84356 KB Output is correct
4 Correct 678 ms 84392 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7184 KB Output is correct
2 Correct 702 ms 84368 KB Output is correct
3 Correct 704 ms 84356 KB Output is correct
4 Correct 678 ms 84392 KB Output is correct
5 Correct 44 ms 7232 KB Output is correct
6 Correct 1914 ms 84356 KB Output is correct
7 Correct 866 ms 87380 KB Output is correct
8 Correct 2958 ms 86856 KB Output is correct
9 Correct 2936 ms 86920 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7236 KB Output is correct
2 Correct 701 ms 70432 KB Output is correct
3 Correct 795 ms 70520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7236 KB Output is correct
2 Correct 701 ms 70432 KB Output is correct
3 Correct 795 ms 70520 KB Output is correct
4 Correct 45 ms 7236 KB Output is correct
5 Correct 1157 ms 70404 KB Output is correct
6 Correct 1867 ms 70372 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7200 KB Output is correct
2 Correct 670 ms 84456 KB Output is correct
3 Correct 692 ms 84500 KB Output is correct
4 Correct 654 ms 84640 KB Output is correct
5 Correct 46 ms 7312 KB Output is correct
6 Correct 739 ms 70316 KB Output is correct
7 Correct 783 ms 70548 KB Output is correct
8 Correct 861 ms 70272 KB Output is correct
9 Correct 730 ms 70264 KB Output is correct
10 Correct 709 ms 75204 KB Output is correct
11 Correct 847 ms 74180 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7200 KB Output is correct
2 Correct 670 ms 84456 KB Output is correct
3 Correct 692 ms 84500 KB Output is correct
4 Correct 654 ms 84640 KB Output is correct
5 Correct 46 ms 7312 KB Output is correct
6 Correct 739 ms 70316 KB Output is correct
7 Correct 783 ms 70548 KB Output is correct
8 Correct 861 ms 70272 KB Output is correct
9 Correct 730 ms 70264 KB Output is correct
10 Correct 709 ms 75204 KB Output is correct
11 Correct 847 ms 74180 KB Output is correct
12 Correct 43 ms 7220 KB Output is correct
13 Correct 1953 ms 84468 KB Output is correct
14 Correct 877 ms 87464 KB Output is correct
15 Correct 2853 ms 87160 KB Output is correct
16 Correct 2893 ms 86908 KB Output is correct
17 Correct 44 ms 8148 KB Output is correct
18 Correct 1176 ms 73184 KB Output is correct
19 Correct 1859 ms 73260 KB Output is correct
20 Correct 1357 ms 72940 KB Output is correct
21 Correct 2811 ms 73216 KB Output is correct
22 Correct 2988 ms 76592 KB Output is correct
23 Correct 2016 ms 78772 KB Output is correct
24 Correct 1122 ms 78836 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7208 KB Output is correct
2 Correct 77 ms 9296 KB Output is correct
3 Correct 104 ms 9424 KB Output is correct
4 Correct 69 ms 9492 KB Output is correct
5 Correct 90 ms 9856 KB Output is correct
6 Correct 99 ms 9400 KB Output is correct
7 Correct 51 ms 7316 KB Output is correct
8 Correct 770 ms 69864 KB Output is correct
9 Correct 780 ms 69900 KB Output is correct
10 Correct 45 ms 7232 KB Output is correct
11 Correct 679 ms 84392 KB Output is correct
12 Correct 685 ms 84456 KB Output is correct
13 Correct 654 ms 84588 KB Output is correct
14 Correct 46 ms 7236 KB Output is correct
15 Correct 706 ms 70348 KB Output is correct
16 Correct 787 ms 70480 KB Output is correct
17 Correct 860 ms 70088 KB Output is correct
18 Correct 726 ms 70228 KB Output is correct
19 Correct 756 ms 75276 KB Output is correct
20 Correct 820 ms 74264 KB Output is correct
21 Correct 751 ms 69504 KB Output is correct
22 Correct 725 ms 69612 KB Output is correct
23 Correct 740 ms 69672 KB Output is correct
24 Correct 756 ms 69564 KB Output is correct
25 Correct 775 ms 73868 KB Output is correct
26 Correct 869 ms 70276 KB Output is correct
27 Correct 821 ms 70220 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7208 KB Output is correct
2 Correct 77 ms 9296 KB Output is correct
3 Correct 104 ms 9424 KB Output is correct
4 Correct 69 ms 9492 KB Output is correct
5 Correct 90 ms 9856 KB Output is correct
6 Correct 99 ms 9400 KB Output is correct
7 Correct 51 ms 7316 KB Output is correct
8 Correct 770 ms 69864 KB Output is correct
9 Correct 780 ms 69900 KB Output is correct
10 Correct 45 ms 7232 KB Output is correct
11 Correct 679 ms 84392 KB Output is correct
12 Correct 685 ms 84456 KB Output is correct
13 Correct 654 ms 84588 KB Output is correct
14 Correct 46 ms 7236 KB Output is correct
15 Correct 706 ms 70348 KB Output is correct
16 Correct 787 ms 70480 KB Output is correct
17 Correct 860 ms 70088 KB Output is correct
18 Correct 726 ms 70228 KB Output is correct
19 Correct 756 ms 75276 KB Output is correct
20 Correct 820 ms 74264 KB Output is correct
21 Correct 751 ms 69504 KB Output is correct
22 Correct 725 ms 69612 KB Output is correct
23 Correct 740 ms 69672 KB Output is correct
24 Correct 756 ms 69564 KB Output is correct
25 Correct 775 ms 73868 KB Output is correct
26 Correct 869 ms 70276 KB Output is correct
27 Correct 821 ms 70220 KB Output is correct
28 Correct 48 ms 7256 KB Output is correct
29 Correct 120 ms 9252 KB Output is correct
30 Correct 111 ms 9420 KB Output is correct
31 Correct 113 ms 9388 KB Output is correct
32 Correct 80 ms 9712 KB Output is correct
33 Correct 131 ms 9412 KB Output is correct
34 Correct 50 ms 7236 KB Output is correct
35 Correct 1466 ms 69992 KB Output is correct
36 Correct 2862 ms 70400 KB Output is correct
37 Correct 3264 ms 70212 KB Output is correct
38 Correct 44 ms 7236 KB Output is correct
39 Correct 1914 ms 84304 KB Output is correct
40 Correct 890 ms 87368 KB Output is correct
41 Correct 2793 ms 86904 KB Output is correct
42 Correct 2849 ms 87080 KB Output is correct
43 Correct 47 ms 8132 KB Output is correct
44 Correct 1141 ms 73356 KB Output is correct
45 Correct 1897 ms 73336 KB Output is correct
46 Correct 1303 ms 73256 KB Output is correct
47 Correct 2670 ms 73184 KB Output is correct
48 Correct 2711 ms 76772 KB Output is correct
49 Correct 1901 ms 78928 KB Output is correct
50 Correct 973 ms 78932 KB Output is correct
51 Correct 2861 ms 72688 KB Output is correct
52 Execution timed out 3521 ms 72888 KB Time limit exceeded
53 Halted 0 ms 0 KB -