oj.uz

답안 #820171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820171 2023-08-10T22:32:23 Z PenguinsAreCute 다리 (APIO19_bridges) C++17
100 / 100
 1621 ms 98004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define HASTC 0
#define B 1000
int par[121010], sz[121010];
int u[121010], v[121010], w[121010];
int t[B+5], f[B+5], s[B+5], ans[B+5];
vi join_edge[B+5];
bool changed[121010];
stack<int> onions;
// onion find disjoint sets (with rollbacks)
int find_set(int x) {
    while(x!=par[x]) x=par[x];
    return x;
}
void onion(int x, int y) {
    x=find_set(x),y=find_set(y);
    if(x==y) {onions.push(-1); return;}
    if(sz[x]<sz[y]) swap(x,y);
    onions.push(y);
    par[y]=x; sz[x]+=sz[y];
}
void rollback() {
    assert(!onions.empty());
    if(onions.top()!=-1) {
        sz[par[onions.top()]]-=sz[onions.top()];
        par[onions.top()]=onions.top();
    }
    onions.pop();
}
void init_bucket() {
    iota(par,par+121010,0);
    fill(sz,sz+121010, 1);
    fill(changed,changed+121010,false);
}
void solvetc(int idx) {
    int n, m, q; cin >> n >> m;
    REP(i,0,m) {cin>>u[i]>>v[i]>>w[i]; u[i]--,v[i]--;}
    cin>>q;
    for(int i=0; i<q; i+=B) {
        init_bucket();
        vi qry, upd, nUpd;
        int j=min(q,i+B);
        REP(k,i,j) {
            cin>>t[k-i]>>f[k-i]>>s[k-i];
            if(t[k-i]==1) {upd.pb(k-i); changed[--f[k-i]]=1;}
            else qry.pb(k-i), f[k-i]--;
        }
        REP(k,0,m) if(!changed[k]) nUpd.pb(k);
        REP(k,i,j) {
            if(t[k-i]==1) w[f[k-i]]=s[k-i];
            else {
                join_edge[k-i].clear();
                for(auto l: upd) if(w[f[l]]>=s[k-i]) join_edge[k-i].pb(f[l]);
            }
        }
        sort(qry.begin(),qry.end(),[](int a, int b){return s[a]>s[b];});
        sort(nUpd.begin(),nUpd.end(),[](int a, int b){return w[a]>w[b];});
        int ptr=0;
        for(auto k: qry) {
            while(ptr<nUpd.size()&&w[nUpd[ptr]]>=s[k]) {
                onion(u[nUpd[ptr]],v[nUpd[ptr]]);
                ptr++;
            }
            for(auto l: join_edge[k]) onion(u[l],v[l]);
            ans[k]=sz[find_set(f[k])];
            for(auto l: join_edge[k]) rollback();
        }
        REP(k,i,j) if(t[k-i]==2) cout<<ans[k-i]<<"\n";
    }
}
int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    int tc;
    if(HASTC) cin>>tc;
    else tc=1;
    for(int i=0;i<tc;i++) solvetc(i);    
}

Compilation message

bridges.cpp: In function 'void solvetc(long long int)':
bridges.cpp:77:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             while(ptr<nUpd.size()&&w[nUpd[ptr]]>=s[k]) {
      |                   ~~~^~~~~~~~~~~~
bridges.cpp:83:22: warning: unused variable 'l' [-Wunused-variable]
   83 |             for(auto l: join_edge[k]) rollback();
      |                      ^

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 33 ms 6872 KB Output is correct
4 Correct 5 ms 2516 KB Output is correct
5 Correct 32 ms 7200 KB Output is correct
6 Correct 25 ms 6600 KB Output is correct
7 Correct 32 ms 8288 KB Output is correct
8 Correct 35 ms 6732 KB Output is correct
9 Correct 37 ms 9976 KB Output is correct
10 Correct 35 ms 7032 KB Output is correct
11 Correct 35 ms 6732 KB Output is correct
12 Correct 42 ms 7064 KB Output is correct
13 Correct 39 ms 6912 KB Output is correct
14 Correct 36 ms 6704 KB Output is correct
15 Correct 40 ms 6744 KB Output is correct
16 Correct 33 ms 9164 KB Output is correct
17 Correct 33 ms 8244 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 889 ms 52300 KB Output is correct
2 Correct 865 ms 52308 KB Output is correct
3 Correct 884 ms 52436 KB Output is correct
4 Correct 911 ms 52348 KB Output is correct
5 Correct 915 ms 52656 KB Output is correct
6 Correct 1054 ms 55644 KB Output is correct
7 Correct 1097 ms 55572 KB Output is correct
8 Correct 1101 ms 55632 KB Output is correct
9 Correct 39 ms 3948 KB Output is correct
10 Correct 557 ms 54696 KB Output is correct
11 Correct 574 ms 54732 KB Output is correct
12 Correct 769 ms 48908 KB Output is correct
13 Correct 753 ms 55192 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 676 ms 37272 KB Output is correct
2 Correct 422 ms 18880 KB Output is correct
3 Correct 732 ms 40504 KB Output is correct
4 Correct 652 ms 37440 KB Output is correct
5 Correct 39 ms 3844 KB Output is correct
6 Correct 714 ms 37280 KB Output is correct
7 Correct 613 ms 36872 KB Output is correct
8 Correct 552 ms 36732 KB Output is correct
9 Correct 472 ms 33900 KB Output is correct
10 Correct 445 ms 33948 KB Output is correct
11 Correct 519 ms 39776 KB Output is correct
12 Correct 469 ms 39652 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1245 ms 91840 KB Output is correct
2 Correct 38 ms 3948 KB Output is correct
3 Correct 143 ms 15988 KB Output is correct
4 Correct 66 ms 16116 KB Output is correct
5 Correct 607 ms 90496 KB Output is correct
6 Correct 1240 ms 91876 KB Output is correct
7 Correct 617 ms 90528 KB Output is correct
8 Correct 589 ms 47952 KB Output is correct
9 Correct 561 ms 48064 KB Output is correct
10 Correct 569 ms 47992 KB Output is correct
11 Correct 913 ms 70068 KB Output is correct
12 Correct 883 ms 70176 KB Output is correct
13 Correct 940 ms 70160 KB Output is correct
14 Correct 563 ms 90548 KB Output is correct
15 Correct 574 ms 90680 KB Output is correct
16 Correct 1242 ms 91008 KB Output is correct
17 Correct 1266 ms 90912 KB Output is correct
18 Correct 1255 ms 91364 KB Output is correct
19 Correct 1282 ms 91144 KB Output is correct
20 Correct 1042 ms 77360 KB Output is correct
21 Correct 1043 ms 77268 KB Output is correct
22 Correct 1185 ms 87652 KB Output is correct
23 Correct 688 ms 73584 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 889 ms 52300 KB Output is correct
2 Correct 865 ms 52308 KB Output is correct
3 Correct 884 ms 52436 KB Output is correct
4 Correct 911 ms 52348 KB Output is correct
5 Correct 915 ms 52656 KB Output is correct
6 Correct 1054 ms 55644 KB Output is correct
7 Correct 1097 ms 55572 KB Output is correct
8 Correct 1101 ms 55632 KB Output is correct
9 Correct 39 ms 3948 KB Output is correct
10 Correct 557 ms 54696 KB Output is correct
11 Correct 574 ms 54732 KB Output is correct
12 Correct 769 ms 48908 KB Output is correct
13 Correct 753 ms 55192 KB Output is correct
14 Correct 676 ms 37272 KB Output is correct
15 Correct 422 ms 18880 KB Output is correct
16 Correct 732 ms 40504 KB Output is correct
17 Correct 652 ms 37440 KB Output is correct
18 Correct 39 ms 3844 KB Output is correct
19 Correct 714 ms 37280 KB Output is correct
20 Correct 613 ms 36872 KB Output is correct
21 Correct 552 ms 36732 KB Output is correct
22 Correct 472 ms 33900 KB Output is correct
23 Correct 445 ms 33948 KB Output is correct
24 Correct 519 ms 39776 KB Output is correct
25 Correct 469 ms 39652 KB Output is correct
26 Correct 925 ms 52552 KB Output is correct
27 Correct 997 ms 55632 KB Output is correct
28 Correct 948 ms 52524 KB Output is correct
29 Correct 746 ms 51776 KB Output is correct
30 Correct 997 ms 55472 KB Output is correct
31 Correct 1101 ms 55552 KB Output is correct
32 Correct 1020 ms 55544 KB Output is correct
33 Correct 905 ms 52268 KB Output is correct
34 Correct 928 ms 52312 KB Output is correct
35 Correct 939 ms 52328 KB Output is correct
36 Correct 750 ms 51724 KB Output is correct
37 Correct 739 ms 51588 KB Output is correct
38 Correct 732 ms 51668 KB Output is correct
39 Correct 634 ms 48868 KB Output is correct
40 Correct 625 ms 48896 KB Output is correct
41 Correct 623 ms 48852 KB Output is correct
42 Correct 628 ms 52896 KB Output is correct
43 Correct 629 ms 52812 KB Output is correct
44 Correct 622 ms 52752 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 33 ms 6872 KB Output is correct
4 Correct 5 ms 2516 KB Output is correct
5 Correct 32 ms 7200 KB Output is correct
6 Correct 25 ms 6600 KB Output is correct
7 Correct 32 ms 8288 KB Output is correct
8 Correct 35 ms 6732 KB Output is correct
9 Correct 37 ms 9976 KB Output is correct
10 Correct 35 ms 7032 KB Output is correct
11 Correct 35 ms 6732 KB Output is correct
12 Correct 42 ms 7064 KB Output is correct
13 Correct 39 ms 6912 KB Output is correct
14 Correct 36 ms 6704 KB Output is correct
15 Correct 40 ms 6744 KB Output is correct
16 Correct 33 ms 9164 KB Output is correct
17 Correct 33 ms 8244 KB Output is correct
18 Correct 889 ms 52300 KB Output is correct
19 Correct 865 ms 52308 KB Output is correct
20 Correct 884 ms 52436 KB Output is correct
21 Correct 911 ms 52348 KB Output is correct
22 Correct 915 ms 52656 KB Output is correct
23 Correct 1054 ms 55644 KB Output is correct
24 Correct 1097 ms 55572 KB Output is correct
25 Correct 1101 ms 55632 KB Output is correct
26 Correct 39 ms 3948 KB Output is correct
27 Correct 557 ms 54696 KB Output is correct
28 Correct 574 ms 54732 KB Output is correct
29 Correct 769 ms 48908 KB Output is correct
30 Correct 753 ms 55192 KB Output is correct
31 Correct 676 ms 37272 KB Output is correct
32 Correct 422 ms 18880 KB Output is correct
33 Correct 732 ms 40504 KB Output is correct
34 Correct 652 ms 37440 KB Output is correct
35 Correct 39 ms 3844 KB Output is correct
36 Correct 714 ms 37280 KB Output is correct
37 Correct 613 ms 36872 KB Output is correct
38 Correct 552 ms 36732 KB Output is correct
39 Correct 472 ms 33900 KB Output is correct
40 Correct 445 ms 33948 KB Output is correct
41 Correct 519 ms 39776 KB Output is correct
42 Correct 469 ms 39652 KB Output is correct
43 Correct 1245 ms 91840 KB Output is correct
44 Correct 38 ms 3948 KB Output is correct
45 Correct 143 ms 15988 KB Output is correct
46 Correct 66 ms 16116 KB Output is correct
47 Correct 607 ms 90496 KB Output is correct
48 Correct 1240 ms 91876 KB Output is correct
49 Correct 617 ms 90528 KB Output is correct
50 Correct 589 ms 47952 KB Output is correct
51 Correct 561 ms 48064 KB Output is correct
52 Correct 569 ms 47992 KB Output is correct
53 Correct 913 ms 70068 KB Output is correct
54 Correct 883 ms 70176 KB Output is correct
55 Correct 940 ms 70160 KB Output is correct
56 Correct 563 ms 90548 KB Output is correct
57 Correct 574 ms 90680 KB Output is correct
58 Correct 1242 ms 91008 KB Output is correct
59 Correct 1266 ms 90912 KB Output is correct
60 Correct 1255 ms 91364 KB Output is correct
61 Correct 1282 ms 91144 KB Output is correct
62 Correct 1042 ms 77360 KB Output is correct
63 Correct 1043 ms 77268 KB Output is correct
64 Correct 1185 ms 87652 KB Output is correct
65 Correct 688 ms 73584 KB Output is correct
66 Correct 925 ms 52552 KB Output is correct
67 Correct 997 ms 55632 KB Output is correct
68 Correct 948 ms 52524 KB Output is correct
69 Correct 746 ms 51776 KB Output is correct
70 Correct 997 ms 55472 KB Output is correct
71 Correct 1101 ms 55552 KB Output is correct
72 Correct 1020 ms 55544 KB Output is correct
73 Correct 905 ms 52268 KB Output is correct
74 Correct 928 ms 52312 KB Output is correct
75 Correct 939 ms 52328 KB Output is correct
76 Correct 750 ms 51724 KB Output is correct
77 Correct 739 ms 51588 KB Output is correct
78 Correct 732 ms 51668 KB Output is correct
79 Correct 634 ms 48868 KB Output is correct
80 Correct 625 ms 48896 KB Output is correct
81 Correct 623 ms 48852 KB Output is correct
82 Correct 628 ms 52896 KB Output is correct
83 Correct 629 ms 52812 KB Output is correct
84 Correct 622 ms 52752 KB Output is correct
85 Correct 1583 ms 95880 KB Output is correct
86 Correct 158 ms 19668 KB Output is correct
87 Correct 92 ms 21956 KB Output is correct
88 Correct 880 ms 97980 KB Output is correct
89 Correct 1575 ms 96192 KB Output is correct
90 Correct 887 ms 98004 KB Output is correct
91 Correct 936 ms 52296 KB Output is correct
92 Correct 966 ms 52244 KB Output is correct
93 Correct 1172 ms 54980 KB Output is correct
94 Correct 1314 ms 74516 KB Output is correct
95 Correct 1288 ms 74480 KB Output is correct
96 Correct 1441 ms 77620 KB Output is correct
97 Correct 703 ms 91388 KB Output is correct
98 Correct 731 ms 97468 KB Output is correct
99 Correct 1606 ms 95604 KB Output is correct
100 Correct 1616 ms 95020 KB Output is correct
101 Correct 1621 ms 95512 KB Output is correct
102 Correct 1605 ms 95432 KB Output is correct
103 Correct 1537 ms 85028 KB Output is correct
104 Correct 1514 ms 84908 KB Output is correct
105 Correct 1245 ms 84472 KB Output is correct
106 Correct 1030 ms 77016 KB Output is correct
107 Correct 1195 ms 78292 KB Output is correct
108 Correct 1579 ms 92900 KB Output is correct
109 Correct 1074 ms 81228 KB Output is correct