oj.uz

답안 #704184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704184 2023-03-01T22:00:42 Z AmirElarbi 다리 (APIO19_bridges) C++14
100 / 100
 2176 ms 32516 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
const int nax2 = 5e4+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
const int batch = 1000;
int x[nax], y[nax], w[nax], t[nax], b[nax], r[nax];
int sz[nax], par[nax], ans[nax];
vi un[batch];
stack<int> st;
bool changed[nax];
int findpar(int u){
    if(par[u] == u) return u;
    return u = findpar(par[u]);
}
bool isSameSet(int u, int v){
    return (findpar(u) == findpar(v));
}
void unionSet(int u, int v){
    u = findpar(u), v = findpar(v);
    if(u == v) return;
    if(sz[u] > sz[v]) swap(u,v);
    st.push(u);
    sz[v] += sz[u];
    par[u] = v; 
}
void rollback(int steps){
    while(st.size() > steps){
        int cur = st.top();
        sz[par[cur]] -= sz[cur];
        par[cur] = cur;
        st.pop();
    }
}
bool cmp(int a, int b){
    return r[a] > r[b];
}
bool cmp2(int a, int b){
    return w[a] > w[b];
}
int main(){
    optimise;
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> x[i] >> y[i] >> w[i];
    int q; cin >> q;
    for(int i = 0; i < q; i++) cin >> t[i] >> b[i] >> r[i];
    for(int l = 0; l < q; l += batch){
        int rg = min(q, l+batch);
        memset(changed, 0, sizeof changed);
        for(int i = 0; i < nax2; i++) sz[i] = 1, par[i] = i;
        vi ask, update, unchanged;
        for (int i = l; i < rg; ++i)
        {
            if(t[i] == 1){
                changed[b[i]] = 1;
                update.pb(i);
            } else ask.pb(i);
        }
        for(int i = 1; i <= m; i++) if(!changed[i]) unchanged.pb(i);
        sort(ask.begin(), ask.end(), cmp);
        sort(unchanged.begin(), unchanged.end(), cmp2);
        for (int i = l; i < rg; ++i)
        {
            if(t[i] == 1) {
                w[b[i]] = r[i];
            } else {
                un[i-l].clear();
                for(auto j : update) if(w[b[j]] >= r[i]) un[i-l].pb(b[j]);
            }
        }
        int cnt = 0;
        for(auto j : ask){
            while(cnt < unchanged.size() && r[j] <= w[unchanged[cnt]]) 
            {
                unionSet(x[unchanged[cnt]], y[unchanged[cnt]]);
                cnt++;
            }
            int prv = st.size();
            for(auto i : un[j-l]) unionSet(x[i], y[i]);
            ans[j] = sz[findpar(b[j])];
            rollback(prv);
        }
    }
    for(int i = 0; i <q ; i++) if(t[i] == 2) cout << ans[i] << endl;
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:52:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     while(st.size() > steps){
      |           ~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(cnt < unchanged.size() && r[j] <= w[unchanged[cnt]])
      |                   ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 38 ms 3296 KB Output is correct
4 Correct 17 ms 1236 KB Output is correct
5 Correct 40 ms 3512 KB Output is correct
6 Correct 31 ms 3204 KB Output is correct
7 Correct 36 ms 4068 KB Output is correct
8 Correct 42 ms 3196 KB Output is correct
9 Correct 46 ms 4812 KB Output is correct
10 Correct 39 ms 3360 KB Output is correct
11 Correct 39 ms 3312 KB Output is correct
12 Correct 47 ms 3404 KB Output is correct
13 Correct 47 ms 3372 KB Output is correct
14 Correct 42 ms 3312 KB Output is correct
15 Correct 46 ms 3276 KB Output is correct
16 Correct 42 ms 4540 KB Output is correct
17 Correct 44 ms 3992 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1322 ms 28964 KB Output is correct
2 Correct 1334 ms 28980 KB Output is correct
3 Correct 1342 ms 28856 KB Output is correct
4 Correct 1359 ms 29068 KB Output is correct
5 Correct 1366 ms 29152 KB Output is correct
6 Correct 1973 ms 30652 KB Output is correct
7 Correct 1981 ms 30500 KB Output is correct
8 Correct 2091 ms 30676 KB Output is correct
9 Correct 142 ms 3840 KB Output is correct
10 Correct 1148 ms 29532 KB Output is correct
11 Correct 1061 ms 29636 KB Output is correct
12 Correct 1265 ms 27332 KB Output is correct
13 Correct 1203 ms 30308 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1093 ms 21276 KB Output is correct
2 Correct 825 ms 11848 KB Output is correct
3 Correct 1291 ms 23120 KB Output is correct
4 Correct 1071 ms 21380 KB Output is correct
5 Correct 144 ms 3892 KB Output is correct
6 Correct 1225 ms 21284 KB Output is correct
7 Correct 993 ms 21108 KB Output is correct
8 Correct 873 ms 20920 KB Output is correct
9 Correct 781 ms 19576 KB Output is correct
10 Correct 713 ms 19528 KB Output is correct
11 Correct 736 ms 22400 KB Output is correct
12 Correct 656 ms 22432 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1683 ms 28676 KB Output is correct
2 Correct 141 ms 3900 KB Output is correct
3 Correct 171 ms 4912 KB Output is correct
4 Correct 97 ms 5056 KB Output is correct
5 Correct 941 ms 27264 KB Output is correct
6 Correct 1663 ms 28740 KB Output is correct
7 Correct 906 ms 27152 KB Output is correct
8 Correct 860 ms 26812 KB Output is correct
9 Correct 851 ms 26744 KB Output is correct
10 Correct 854 ms 26788 KB Output is correct
11 Correct 1291 ms 27896 KB Output is correct
12 Correct 1265 ms 28164 KB Output is correct
13 Correct 1285 ms 28176 KB Output is correct
14 Correct 854 ms 27380 KB Output is correct
15 Correct 896 ms 27224 KB Output is correct
16 Correct 1669 ms 29028 KB Output is correct
17 Correct 1680 ms 28872 KB Output is correct
18 Correct 1699 ms 29204 KB Output is correct
19 Correct 1673 ms 29060 KB Output is correct
20 Correct 1427 ms 28376 KB Output is correct
21 Correct 1419 ms 28408 KB Output is correct
22 Correct 1618 ms 28444 KB Output is correct
23 Correct 986 ms 25172 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1322 ms 28964 KB Output is correct
2 Correct 1334 ms 28980 KB Output is correct
3 Correct 1342 ms 28856 KB Output is correct
4 Correct 1359 ms 29068 KB Output is correct
5 Correct 1366 ms 29152 KB Output is correct
6 Correct 1973 ms 30652 KB Output is correct
7 Correct 1981 ms 30500 KB Output is correct
8 Correct 2091 ms 30676 KB Output is correct
9 Correct 142 ms 3840 KB Output is correct
10 Correct 1148 ms 29532 KB Output is correct
11 Correct 1061 ms 29636 KB Output is correct
12 Correct 1265 ms 27332 KB Output is correct
13 Correct 1203 ms 30308 KB Output is correct
14 Correct 1093 ms 21276 KB Output is correct
15 Correct 825 ms 11848 KB Output is correct
16 Correct 1291 ms 23120 KB Output is correct
17 Correct 1071 ms 21380 KB Output is correct
18 Correct 144 ms 3892 KB Output is correct
19 Correct 1225 ms 21284 KB Output is correct
20 Correct 993 ms 21108 KB Output is correct
21 Correct 873 ms 20920 KB Output is correct
22 Correct 781 ms 19576 KB Output is correct
23 Correct 713 ms 19528 KB Output is correct
24 Correct 736 ms 22400 KB Output is correct
25 Correct 656 ms 22432 KB Output is correct
26 Correct 1443 ms 29192 KB Output is correct
27 Correct 1682 ms 30524 KB Output is correct
28 Correct 1405 ms 29108 KB Output is correct
29 Correct 1065 ms 28648 KB Output is correct
30 Correct 1603 ms 30600 KB Output is correct
31 Correct 1634 ms 30608 KB Output is correct
32 Correct 1637 ms 30632 KB Output is correct
33 Correct 1393 ms 28840 KB Output is correct
34 Correct 1390 ms 28860 KB Output is correct
35 Correct 1407 ms 29104 KB Output is correct
36 Correct 1076 ms 28672 KB Output is correct
37 Correct 1071 ms 28580 KB Output is correct
38 Correct 1109 ms 28568 KB Output is correct
39 Correct 948 ms 27220 KB Output is correct
40 Correct 942 ms 27296 KB Output is correct
41 Correct 940 ms 27136 KB Output is correct
42 Correct 877 ms 29172 KB Output is correct
43 Correct 847 ms 29080 KB Output is correct
44 Correct 848 ms 29068 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 38 ms 3296 KB Output is correct
4 Correct 17 ms 1236 KB Output is correct
5 Correct 40 ms 3512 KB Output is correct
6 Correct 31 ms 3204 KB Output is correct
7 Correct 36 ms 4068 KB Output is correct
8 Correct 42 ms 3196 KB Output is correct
9 Correct 46 ms 4812 KB Output is correct
10 Correct 39 ms 3360 KB Output is correct
11 Correct 39 ms 3312 KB Output is correct
12 Correct 47 ms 3404 KB Output is correct
13 Correct 47 ms 3372 KB Output is correct
14 Correct 42 ms 3312 KB Output is correct
15 Correct 46 ms 3276 KB Output is correct
16 Correct 42 ms 4540 KB Output is correct
17 Correct 44 ms 3992 KB Output is correct
18 Correct 1322 ms 28964 KB Output is correct
19 Correct 1334 ms 28980 KB Output is correct
20 Correct 1342 ms 28856 KB Output is correct
21 Correct 1359 ms 29068 KB Output is correct
22 Correct 1366 ms 29152 KB Output is correct
23 Correct 1973 ms 30652 KB Output is correct
24 Correct 1981 ms 30500 KB Output is correct
25 Correct 2091 ms 30676 KB Output is correct
26 Correct 142 ms 3840 KB Output is correct
27 Correct 1148 ms 29532 KB Output is correct
28 Correct 1061 ms 29636 KB Output is correct
29 Correct 1265 ms 27332 KB Output is correct
30 Correct 1203 ms 30308 KB Output is correct
31 Correct 1093 ms 21276 KB Output is correct
32 Correct 825 ms 11848 KB Output is correct
33 Correct 1291 ms 23120 KB Output is correct
34 Correct 1071 ms 21380 KB Output is correct
35 Correct 144 ms 3892 KB Output is correct
36 Correct 1225 ms 21284 KB Output is correct
37 Correct 993 ms 21108 KB Output is correct
38 Correct 873 ms 20920 KB Output is correct
39 Correct 781 ms 19576 KB Output is correct
40 Correct 713 ms 19528 KB Output is correct
41 Correct 736 ms 22400 KB Output is correct
42 Correct 656 ms 22432 KB Output is correct
43 Correct 1683 ms 28676 KB Output is correct
44 Correct 141 ms 3900 KB Output is correct
45 Correct 171 ms 4912 KB Output is correct
46 Correct 97 ms 5056 KB Output is correct
47 Correct 941 ms 27264 KB Output is correct
48 Correct 1663 ms 28740 KB Output is correct
49 Correct 906 ms 27152 KB Output is correct
50 Correct 860 ms 26812 KB Output is correct
51 Correct 851 ms 26744 KB Output is correct
52 Correct 854 ms 26788 KB Output is correct
53 Correct 1291 ms 27896 KB Output is correct
54 Correct 1265 ms 28164 KB Output is correct
55 Correct 1285 ms 28176 KB Output is correct
56 Correct 854 ms 27380 KB Output is correct
57 Correct 896 ms 27224 KB Output is correct
58 Correct 1669 ms 29028 KB Output is correct
59 Correct 1680 ms 28872 KB Output is correct
60 Correct 1699 ms 29204 KB Output is correct
61 Correct 1673 ms 29060 KB Output is correct
62 Correct 1427 ms 28376 KB Output is correct
63 Correct 1419 ms 28408 KB Output is correct
64 Correct 1618 ms 28444 KB Output is correct
65 Correct 986 ms 25172 KB Output is correct
66 Correct 1443 ms 29192 KB Output is correct
67 Correct 1682 ms 30524 KB Output is correct
68 Correct 1405 ms 29108 KB Output is correct
69 Correct 1065 ms 28648 KB Output is correct
70 Correct 1603 ms 30600 KB Output is correct
71 Correct 1634 ms 30608 KB Output is correct
72 Correct 1637 ms 30632 KB Output is correct
73 Correct 1393 ms 28840 KB Output is correct
74 Correct 1390 ms 28860 KB Output is correct
75 Correct 1407 ms 29104 KB Output is correct
76 Correct 1076 ms 28672 KB Output is correct
77 Correct 1071 ms 28580 KB Output is correct
78 Correct 1109 ms 28568 KB Output is correct
79 Correct 948 ms 27220 KB Output is correct
80 Correct 942 ms 27296 KB Output is correct
81 Correct 940 ms 27136 KB Output is correct
82 Correct 877 ms 29172 KB Output is correct
83 Correct 847 ms 29080 KB Output is correct
84 Correct 848 ms 29068 KB Output is correct
85 Correct 2049 ms 30956 KB Output is correct
86 Correct 202 ms 7008 KB Output is correct
87 Correct 139 ms 8360 KB Output is correct
88 Correct 1268 ms 31264 KB Output is correct
89 Correct 2037 ms 31032 KB Output is correct
90 Correct 1287 ms 31160 KB Output is correct
91 Correct 1440 ms 28876 KB Output is correct
92 Correct 1429 ms 28904 KB Output is correct
93 Correct 2021 ms 30336 KB Output is correct
94 Correct 1694 ms 30472 KB Output is correct
95 Correct 1700 ms 30540 KB Output is correct
96 Correct 1969 ms 31952 KB Output is correct
97 Correct 1041 ms 27768 KB Output is correct
98 Correct 1030 ms 31004 KB Output is correct
99 Correct 2039 ms 31504 KB Output is correct
100 Correct 2031 ms 31264 KB Output is correct
101 Correct 2102 ms 31344 KB Output is correct
102 Correct 2092 ms 31360 KB Output is correct
103 Correct 2176 ms 32516 KB Output is correct
104 Correct 2162 ms 32252 KB Output is correct
105 Correct 1624 ms 32348 KB Output is correct
106 Correct 1327 ms 31532 KB Output is correct
107 Correct 1629 ms 28928 KB Output is correct
108 Correct 2075 ms 31164 KB Output is correct
109 Correct 1506 ms 28928 KB Output is correct