oj.uz

Submission #425831

# Submission time Handle Problem Language Result Execution time Memory
425831 2021-06-13T11:46:29 Z duality Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 35272 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 = 0.3*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: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 52 ms 4420 KB Output is correct
2 Correct 104 ms 5224 KB Output is correct
3 Correct 106 ms 5224 KB Output is correct
4 Correct 109 ms 5292 KB Output is correct
5 Correct 123 ms 5420 KB Output is correct
6 Correct 105 ms 5300 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4420 KB Output is correct
2 Correct 104 ms 5224 KB Output is correct
3 Correct 106 ms 5224 KB Output is correct
4 Correct 109 ms 5292 KB Output is correct
5 Correct 123 ms 5420 KB Output is correct
6 Correct 105 ms 5300 KB Output is correct
7 Correct 53 ms 4448 KB Output is correct
8 Correct 135 ms 5112 KB Output is correct
9 Correct 112 ms 5312 KB Output is correct
10 Correct 163 ms 5208 KB Output is correct
11 Correct 135 ms 5316 KB Output is correct
12 Correct 117 ms 5332 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4420 KB Output is correct
2 Correct 1668 ms 28940 KB Output is correct
3 Correct 1720 ms 28732 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4420 KB Output is correct
2 Correct 1668 ms 28940 KB Output is correct
3 Correct 1720 ms 28732 KB Output is correct
4 Correct 47 ms 4396 KB Output is correct
5 Correct 1981 ms 28704 KB Output is correct
6 Correct 2137 ms 28912 KB Output is correct
7 Correct 2420 ms 28920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4420 KB Output is correct
2 Correct 1766 ms 35176 KB Output is correct
3 Correct 1764 ms 35188 KB Output is correct
4 Correct 1763 ms 35176 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4420 KB Output is correct
2 Correct 1766 ms 35176 KB Output is correct
3 Correct 1764 ms 35188 KB Output is correct
4 Correct 1763 ms 35176 KB Output is correct
5 Correct 45 ms 4380 KB Output is correct
6 Execution timed out 3579 ms 35020 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4548 KB Output is correct
2 Correct 1863 ms 28596 KB Output is correct
3 Correct 1940 ms 29016 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4548 KB Output is correct
2 Correct 1863 ms 28596 KB Output is correct
3 Correct 1940 ms 29016 KB Output is correct
4 Correct 47 ms 4420 KB Output is correct
5 Correct 2321 ms 28536 KB Output is correct
6 Correct 2668 ms 28896 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4424 KB Output is correct
2 Correct 1758 ms 35272 KB Output is correct
3 Correct 1752 ms 35112 KB Output is correct
4 Correct 1800 ms 35044 KB Output is correct
5 Correct 45 ms 4420 KB Output is correct
6 Correct 1855 ms 28600 KB Output is correct
7 Correct 1939 ms 29080 KB Output is correct
8 Correct 2139 ms 29316 KB Output is correct
9 Correct 1811 ms 29420 KB Output is correct
10 Correct 1838 ms 33128 KB Output is correct
11 Correct 2078 ms 32668 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4424 KB Output is correct
2 Correct 1758 ms 35272 KB Output is correct
3 Correct 1752 ms 35112 KB Output is correct
4 Correct 1800 ms 35044 KB Output is correct
5 Correct 45 ms 4420 KB Output is correct
6 Correct 1855 ms 28600 KB Output is correct
7 Correct 1939 ms 29080 KB Output is correct
8 Correct 2139 ms 29316 KB Output is correct
9 Correct 1811 ms 29420 KB Output is correct
10 Correct 1838 ms 33128 KB Output is correct
11 Correct 2078 ms 32668 KB Output is correct
12 Correct 49 ms 4428 KB Output is correct
13 Execution timed out 3571 ms 34856 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4420 KB Output is correct
2 Correct 100 ms 5360 KB Output is correct
3 Correct 106 ms 5284 KB Output is correct
4 Correct 109 ms 5288 KB Output is correct
5 Correct 120 ms 5384 KB Output is correct
6 Correct 112 ms 5316 KB Output is correct
7 Correct 63 ms 4420 KB Output is correct
8 Correct 1697 ms 28764 KB Output is correct
9 Correct 1652 ms 28848 KB Output is correct
10 Correct 45 ms 4400 KB Output is correct
11 Correct 1868 ms 35172 KB Output is correct
12 Correct 1761 ms 35132 KB Output is correct
13 Correct 1750 ms 35056 KB Output is correct
14 Correct 47 ms 4420 KB Output is correct
15 Correct 1862 ms 28464 KB Output is correct
16 Correct 1949 ms 29052 KB Output is correct
17 Correct 2176 ms 29480 KB Output is correct
18 Correct 1828 ms 29400 KB Output is correct
19 Correct 1848 ms 33120 KB Output is correct
20 Correct 2115 ms 32640 KB Output is correct
21 Correct 1682 ms 28472 KB Output is correct
22 Correct 1707 ms 28612 KB Output is correct
23 Correct 1734 ms 29092 KB Output is correct
24 Correct 1741 ms 28924 KB Output is correct
25 Correct 1876 ms 30140 KB Output is correct
26 Correct 2015 ms 28348 KB Output is correct
27 Correct 1936 ms 28360 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4420 KB Output is correct
2 Correct 100 ms 5360 KB Output is correct
3 Correct 106 ms 5284 KB Output is correct
4 Correct 109 ms 5288 KB Output is correct
5 Correct 120 ms 5384 KB Output is correct
6 Correct 112 ms 5316 KB Output is correct
7 Correct 63 ms 4420 KB Output is correct
8 Correct 1697 ms 28764 KB Output is correct
9 Correct 1652 ms 28848 KB Output is correct
10 Correct 45 ms 4400 KB Output is correct
11 Correct 1868 ms 35172 KB Output is correct
12 Correct 1761 ms 35132 KB Output is correct
13 Correct 1750 ms 35056 KB Output is correct
14 Correct 47 ms 4420 KB Output is correct
15 Correct 1862 ms 28464 KB Output is correct
16 Correct 1949 ms 29052 KB Output is correct
17 Correct 2176 ms 29480 KB Output is correct
18 Correct 1828 ms 29400 KB Output is correct
19 Correct 1848 ms 33120 KB Output is correct
20 Correct 2115 ms 32640 KB Output is correct
21 Correct 1682 ms 28472 KB Output is correct
22 Correct 1707 ms 28612 KB Output is correct
23 Correct 1734 ms 29092 KB Output is correct
24 Correct 1741 ms 28924 KB Output is correct
25 Correct 1876 ms 30140 KB Output is correct
26 Correct 2015 ms 28348 KB Output is correct
27 Correct 1936 ms 28360 KB Output is correct
28 Correct 47 ms 4360 KB Output is correct
29 Correct 136 ms 5164 KB Output is correct
30 Correct 116 ms 5316 KB Output is correct
31 Correct 170 ms 5220 KB Output is correct
32 Correct 114 ms 5440 KB Output is correct
33 Correct 113 ms 5292 KB Output is correct
34 Correct 50 ms 4384 KB Output is correct
35 Correct 1893 ms 28892 KB Output is correct
36 Correct 2055 ms 28980 KB Output is correct
37 Correct 2288 ms 28860 KB Output is correct
38 Correct 45 ms 4336 KB Output is correct
39 Execution timed out 3572 ms 35044 KB Time limit exceeded
40 Halted 0 ms 0 KB -