oj.uz

Submission #130167

# Submission time Handle Problem Language Result Execution time Memory
130167 2019-07-14T06:14:12 Z ae04071 Bridges (APIO19_bridges) C++11
100 / 100
 2937 ms 11676 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using lli = long long;
using pii = pair<int,int>;

struct edge{
    int u,v,w,i,c;
    int l,r;
    bool operator<(const edge &rhs)const {
        return w<rhs.w;
    }
}arr[200000];
struct qd{
    int t,a,b;
    bool operator<(const qd &rhs)const {
        return b<rhs.b;
    }
}qa[100000];

int n,m,q;

struct dsu{
    int pa[50001],sz[50001],tp[50001],ts[50001],tf[50001];
    int ti;
    void init() {
        for(int i=1;i<=n;i++) pa[i]=i, sz[i]=1, tf[i]=-1;
    }
    int find(int cur) {
        return cur==pa[cur] ? cur : pa[cur] = find(pa[cur]);
    }
    void merge(int u,int v) {
        u = find(u); v=find(v);
        if(u!=v) {
            pa[v]=u; sz[u]+=sz[v];
        }
    }
    void tcheck(int cur) {
        if(tf[cur]!=ti) tf[cur]=ti, tp[cur]=pa[cur], ts[cur]=sz[cur];
    }
    int tfind(int cur) {
        tcheck(cur);
        return cur==tp[cur] ? cur : tp[cur] = tfind(tp[cur]);
    }
    void tmerge(int u,int v) {
        u=tfind(u), v=tfind(v);
        if(u!=v) {
            tp[v]=u;
            ts[u] += ts[v];
        }
    }
    int tgetsz(int cur) {
        cur=tfind(cur);
        return ts[cur];
    }
}ds;
int ans[100000],pr[100000];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
        arr[i].w = -arr[i].w;
        arr[i].i = i; arr[i].c = -1;
    }

    scanf("%d",&q);
    for(int i=0;i<m;i++) arr[i].l=-1,arr[i].r=q, pr[i] = i;
    for(int i=0;i<q;i++) {
        scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
        qa[i].b = -qa[i].b;
        if(qa[i].t==1) {
            qa[i].a--;

            int idx = pr[qa[i].a];
            arr[m] = arr[idx];
            arr[m].w = qa[i].b;
            arr[idx].r = i;
            arr[m].l = i;

            pr[qa[i].a] = m++;
        }
    }
    sort(arr,arr+m);

    const int B = 500;
    for(int bi=0;bi*B<q;bi++) {
        vector<pair<qd,int>> a2;
        vector<edge> a1;
        for(int i=bi*B;i<min(bi*B+B, q);i++) {
            if(qa[i].t==2) a2.push_back({qa[i], i});
        }
        sort(a2.begin(),a2.end());

        int s=bi*B, e=min(bi*B+B,q);
        for(int i=0;i<m;i++) {
            if((s<=arr[i].l && arr[i].l<e) || (s<=arr[i].r && arr[i].r<e)) arr[i].c=bi,a1.push_back(arr[i]);
        }

        int ei=0;
        ds.init();
        for(int i=0;i<sz(a2);i++) {
            ds.ti=i;
            for(;ei<m && arr[ei].w <= a2[i].fi.b; ei++) if(arr[ei].c!=bi && arr[ei].l<s && arr[ei].r>=e) {
                ds.merge(arr[ei].u, arr[ei].v);
            }
            for(int j=0;j<sz(a1);j++) {
                if(a1[j].l<=a2[i].se && a2[i].se<=a1[j].r && a1[j].w <= a2[i].fi.b) ds.tmerge(a1[j].u,a1[j].v); 
            }
            ans[a2[i].se] = ds.tgetsz(a2[i].fi.a);
        }
    }

    for(int i=0;i<q;i++) if(qa[i].t==2) printf("%d\n",ans[i]);
    
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
bridges.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 33 ms 888 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 23 ms 860 KB Output is correct
6 Correct 18 ms 888 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 25 ms 1016 KB Output is correct
9 Correct 20 ms 760 KB Output is correct
10 Correct 24 ms 888 KB Output is correct
11 Correct 24 ms 888 KB Output is correct
12 Correct 27 ms 888 KB Output is correct
13 Correct 30 ms 888 KB Output is correct
14 Correct 29 ms 892 KB Output is correct
15 Correct 28 ms 888 KB Output is correct
16 Correct 19 ms 760 KB Output is correct
17 Correct 22 ms 764 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 6404 KB Output is correct
2 Correct 1130 ms 6420 KB Output is correct
3 Correct 1143 ms 6436 KB Output is correct
4 Correct 1364 ms 6520 KB Output is correct
5 Correct 1355 ms 6560 KB Output is correct
6 Correct 2097 ms 6656 KB Output is correct
7 Correct 2130 ms 6740 KB Output is correct
8 Correct 2099 ms 6588 KB Output is correct
9 Correct 48 ms 2424 KB Output is correct
10 Correct 1331 ms 6540 KB Output is correct
11 Correct 1241 ms 6396 KB Output is correct
12 Correct 898 ms 5684 KB Output is correct
13 Correct 1372 ms 7444 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 5584 KB Output is correct
2 Correct 612 ms 4292 KB Output is correct
3 Correct 959 ms 5624 KB Output is correct
4 Correct 902 ms 5500 KB Output is correct
5 Correct 48 ms 2424 KB Output is correct
6 Correct 964 ms 5764 KB Output is correct
7 Correct 860 ms 5504 KB Output is correct
8 Correct 809 ms 5496 KB Output is correct
9 Correct 444 ms 4728 KB Output is correct
10 Correct 410 ms 4472 KB Output is correct
11 Correct 820 ms 6520 KB Output is correct
12 Correct 779 ms 6620 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1452 ms 6836 KB Output is correct
2 Correct 50 ms 2808 KB Output is correct
3 Correct 70 ms 4344 KB Output is correct
4 Correct 60 ms 4344 KB Output is correct
5 Correct 1304 ms 7288 KB Output is correct
6 Correct 1345 ms 7540 KB Output is correct
7 Correct 1309 ms 7308 KB Output is correct
8 Correct 510 ms 5396 KB Output is correct
9 Correct 505 ms 5332 KB Output is correct
10 Correct 515 ms 5536 KB Output is correct
11 Correct 797 ms 6304 KB Output is correct
12 Correct 775 ms 6660 KB Output is correct
13 Correct 805 ms 6492 KB Output is correct
14 Correct 1324 ms 7228 KB Output is correct
15 Correct 1328 ms 7352 KB Output is correct
16 Correct 1265 ms 7596 KB Output is correct
17 Correct 1198 ms 7672 KB Output is correct
18 Correct 1173 ms 7688 KB Output is correct
19 Correct 1158 ms 7568 KB Output is correct
20 Correct 906 ms 6724 KB Output is correct
21 Correct 897 ms 6712 KB Output is correct
22 Correct 1234 ms 7608 KB Output is correct
23 Correct 1002 ms 6692 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 6404 KB Output is correct
2 Correct 1130 ms 6420 KB Output is correct
3 Correct 1143 ms 6436 KB Output is correct
4 Correct 1364 ms 6520 KB Output is correct
5 Correct 1355 ms 6560 KB Output is correct
6 Correct 2097 ms 6656 KB Output is correct
7 Correct 2130 ms 6740 KB Output is correct
8 Correct 2099 ms 6588 KB Output is correct
9 Correct 48 ms 2424 KB Output is correct
10 Correct 1331 ms 6540 KB Output is correct
11 Correct 1241 ms 6396 KB Output is correct
12 Correct 898 ms 5684 KB Output is correct
13 Correct 1372 ms 7444 KB Output is correct
14 Correct 911 ms 5584 KB Output is correct
15 Correct 612 ms 4292 KB Output is correct
16 Correct 959 ms 5624 KB Output is correct
17 Correct 902 ms 5500 KB Output is correct
18 Correct 48 ms 2424 KB Output is correct
19 Correct 964 ms 5764 KB Output is correct
20 Correct 860 ms 5504 KB Output is correct
21 Correct 809 ms 5496 KB Output is correct
22 Correct 444 ms 4728 KB Output is correct
23 Correct 410 ms 4472 KB Output is correct
24 Correct 820 ms 6520 KB Output is correct
25 Correct 779 ms 6620 KB Output is correct
26 Correct 1130 ms 6452 KB Output is correct
27 Correct 2623 ms 6604 KB Output is correct
28 Correct 2056 ms 6564 KB Output is correct
29 Correct 1529 ms 6644 KB Output is correct
30 Correct 2241 ms 6388 KB Output is correct
31 Correct 2124 ms 6436 KB Output is correct
32 Correct 2200 ms 6396 KB Output is correct
33 Correct 1505 ms 6400 KB Output is correct
34 Correct 1611 ms 6392 KB Output is correct
35 Correct 1591 ms 6620 KB Output is correct
36 Correct 1229 ms 6392 KB Output is correct
37 Correct 1205 ms 6416 KB Output is correct
38 Correct 1212 ms 6476 KB Output is correct
39 Correct 713 ms 5508 KB Output is correct
40 Correct 736 ms 5376 KB Output is correct
41 Correct 778 ms 5328 KB Output is correct
42 Correct 1082 ms 7404 KB Output is correct
43 Correct 1081 ms 7672 KB Output is correct
44 Correct 1084 ms 7544 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 33 ms 888 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 23 ms 860 KB Output is correct
6 Correct 18 ms 888 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 25 ms 1016 KB Output is correct
9 Correct 20 ms 760 KB Output is correct
10 Correct 24 ms 888 KB Output is correct
11 Correct 24 ms 888 KB Output is correct
12 Correct 27 ms 888 KB Output is correct
13 Correct 30 ms 888 KB Output is correct
14 Correct 29 ms 892 KB Output is correct
15 Correct 28 ms 888 KB Output is correct
16 Correct 19 ms 760 KB Output is correct
17 Correct 22 ms 764 KB Output is correct
18 Correct 1113 ms 6404 KB Output is correct
19 Correct 1130 ms 6420 KB Output is correct
20 Correct 1143 ms 6436 KB Output is correct
21 Correct 1364 ms 6520 KB Output is correct
22 Correct 1355 ms 6560 KB Output is correct
23 Correct 2097 ms 6656 KB Output is correct
24 Correct 2130 ms 6740 KB Output is correct
25 Correct 2099 ms 6588 KB Output is correct
26 Correct 48 ms 2424 KB Output is correct
27 Correct 1331 ms 6540 KB Output is correct
28 Correct 1241 ms 6396 KB Output is correct
29 Correct 898 ms 5684 KB Output is correct
30 Correct 1372 ms 7444 KB Output is correct
31 Correct 911 ms 5584 KB Output is correct
32 Correct 612 ms 4292 KB Output is correct
33 Correct 959 ms 5624 KB Output is correct
34 Correct 902 ms 5500 KB Output is correct
35 Correct 48 ms 2424 KB Output is correct
36 Correct 964 ms 5764 KB Output is correct
37 Correct 860 ms 5504 KB Output is correct
38 Correct 809 ms 5496 KB Output is correct
39 Correct 444 ms 4728 KB Output is correct
40 Correct 410 ms 4472 KB Output is correct
41 Correct 820 ms 6520 KB Output is correct
42 Correct 779 ms 6620 KB Output is correct
43 Correct 1452 ms 6836 KB Output is correct
44 Correct 50 ms 2808 KB Output is correct
45 Correct 70 ms 4344 KB Output is correct
46 Correct 60 ms 4344 KB Output is correct
47 Correct 1304 ms 7288 KB Output is correct
48 Correct 1345 ms 7540 KB Output is correct
49 Correct 1309 ms 7308 KB Output is correct
50 Correct 510 ms 5396 KB Output is correct
51 Correct 505 ms 5332 KB Output is correct
52 Correct 515 ms 5536 KB Output is correct
53 Correct 797 ms 6304 KB Output is correct
54 Correct 775 ms 6660 KB Output is correct
55 Correct 805 ms 6492 KB Output is correct
56 Correct 1324 ms 7228 KB Output is correct
57 Correct 1328 ms 7352 KB Output is correct
58 Correct 1265 ms 7596 KB Output is correct
59 Correct 1198 ms 7672 KB Output is correct
60 Correct 1173 ms 7688 KB Output is correct
61 Correct 1158 ms 7568 KB Output is correct
62 Correct 906 ms 6724 KB Output is correct
63 Correct 897 ms 6712 KB Output is correct
64 Correct 1234 ms 7608 KB Output is correct
65 Correct 1002 ms 6692 KB Output is correct
66 Correct 1130 ms 6452 KB Output is correct
67 Correct 2623 ms 6604 KB Output is correct
68 Correct 2056 ms 6564 KB Output is correct
69 Correct 1529 ms 6644 KB Output is correct
70 Correct 2241 ms 6388 KB Output is correct
71 Correct 2124 ms 6436 KB Output is correct
72 Correct 2200 ms 6396 KB Output is correct
73 Correct 1505 ms 6400 KB Output is correct
74 Correct 1611 ms 6392 KB Output is correct
75 Correct 1591 ms 6620 KB Output is correct
76 Correct 1229 ms 6392 KB Output is correct
77 Correct 1205 ms 6416 KB Output is correct
78 Correct 1212 ms 6476 KB Output is correct
79 Correct 713 ms 5508 KB Output is correct
80 Correct 736 ms 5376 KB Output is correct
81 Correct 778 ms 5328 KB Output is correct
82 Correct 1082 ms 7404 KB Output is correct
83 Correct 1081 ms 7672 KB Output is correct
84 Correct 1084 ms 7544 KB Output is correct
85 Correct 2747 ms 8372 KB Output is correct
86 Correct 96 ms 5748 KB Output is correct
87 Correct 78 ms 5880 KB Output is correct
88 Correct 2372 ms 10112 KB Output is correct
89 Correct 2724 ms 11580 KB Output is correct
90 Correct 2415 ms 10056 KB Output is correct
91 Correct 1467 ms 8816 KB Output is correct
92 Correct 1611 ms 8928 KB Output is correct
93 Correct 2474 ms 8812 KB Output is correct
94 Correct 1937 ms 9976 KB Output is correct
95 Correct 1880 ms 10240 KB Output is correct
96 Correct 2444 ms 10132 KB Output is correct
97 Correct 1607 ms 9264 KB Output is correct
98 Correct 2145 ms 11136 KB Output is correct
99 Correct 2626 ms 11468 KB Output is correct
100 Correct 2573 ms 11640 KB Output is correct
101 Correct 2533 ms 11668 KB Output is correct
102 Correct 2488 ms 11580 KB Output is correct
103 Correct 2367 ms 10504 KB Output is correct
104 Correct 2395 ms 10636 KB Output is correct
105 Correct 1989 ms 11676 KB Output is correct
106 Correct 1613 ms 11252 KB Output is correct
107 Correct 1263 ms 9512 KB Output is correct
108 Correct 2937 ms 11232 KB Output is correct
109 Correct 2357 ms 9336 KB Output is correct