oj.uz

답안 #372894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372894 2021-03-02T08:08:21 Z jainbot27 다리 (APIO19_bridges) C++17
100 / 100
 2873 ms 125252 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 50011;
const int mxM = mxN*2;
const int BLK = 1000;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
class timer: high_resolution_clock {
    const time_point start_time;
public:
    timer(): start_time(now()) {}
    rep elapsed_time() const { return duration_cast<milliseconds>(now()-start_time).count(); } };

struct RollbackUF {
    int e[mxN]; vector<pii> st;
    //RollbackUF(int n) : e(n, -1) {}
    void init() { memset(e, -1, sizeof(e)); st.clear();}
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : find(e[x]); }
    int time() { return siz(st); }
    void rollback(int t) {
        for (int i = time(); i --> t;)
            e[st[i].first] = st[i].second;
        st.resize(t);
    }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        st.push_back({a, e[a]});
        st.push_back({b, e[b]});
        e[a] += e[b]; e[b] = a;
        return true;
    }
};

int e[mxM][3];
int q[mxM][3];
bool change[mxM];
vi upd[mxM];
int ans[mxM];
//timer TIMER;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, qq;
    cin >> n >> m;
    F0R(i, m){
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        e[i][0]--; e[i][1]--;
    }
    cin >> qq;
    F0R(i, qq){
        cin >> q[i][0] >> q[i][1] >> q[i][2];
        q[i][1]--;
    }
    RollbackUF dsu;
    //cout << "WE GOT HERE" << endl;
    for(int qqq=0; qqq<qq; ){
        //cout << "WE GOT HERE" << endl;
        memset(change, 0, sizeof(change));
        int l = qqq, r = min(qqq+BLK, qq);
        vi same, diff, al;
        dsu.init();
        FOR(i, l, r){
            if(q[i][0]==1){
                change[q[i][1]] = 1;
            }
            else{
                al.pb(i);
            }
        }
        F0R(i, m){
            if(!change[i]) same.pb(i);
            else diff.pb(i);
        }

        FOR(i, l, r){
            if(q[i][0]==1){
                e[q[i][1]][2] = q[i][2];
            }
            else{
                trav(j, diff){
                    if(e[j][2]>=q[i][2]){
                        upd[i].pb(j);
                    }
                }
            }
        }
        sort(all(al), [&](const int& e1, const int& e2){
            return q[e1][2]>q[e2][2];
        });
        sort(all(same), [&](const int& e1, const int& e2){
            return e[e1][2]>e[e2][2];
        });
        int pt = 0;
        trav(i, al){
            //cout << "WE GOT HERE 1" << endl;
            while(pt<siz(same)&&e[same[pt]][2]>=q[i][2]){
                dsu.join(e[same[pt]][0], e[same[pt]][1]);
                pt++;
            }
            //cout << "WE GOT HERE 2" << endl;
            int T = dsu.time();
            trav(j, upd[i]){
                dsu.join(e[j][0], e[j][1]);
            }
            ans[i] = dsu.size(dsu.find(q[i][1]));
            dsu.rollback(T);
        }
        qqq = r;
    }
    F0R(i, qq){
        if(q[i][0]==2){
            cout << ans[i] << nl;
        }
    }
    //cout << TIMER.elapsed_time() << nl;
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 41 ms 8812 KB Output is correct
4 Correct 7 ms 3180 KB Output is correct
5 Correct 15 ms 4844 KB Output is correct
6 Correct 12 ms 4716 KB Output is correct
7 Correct 16 ms 4716 KB Output is correct
8 Correct 17 ms 4588 KB Output is correct
9 Correct 19 ms 5740 KB Output is correct
10 Correct 18 ms 4716 KB Output is correct
11 Correct 17 ms 4716 KB Output is correct
12 Correct 20 ms 5100 KB Output is correct
13 Correct 25 ms 5612 KB Output is correct
14 Correct 22 ms 5228 KB Output is correct
15 Correct 19 ms 4844 KB Output is correct
16 Correct 20 ms 5100 KB Output is correct
17 Correct 18 ms 5100 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 72960 KB Output is correct
2 Correct 1731 ms 72916 KB Output is correct
3 Correct 1759 ms 73320 KB Output is correct
4 Correct 1675 ms 72868 KB Output is correct
5 Correct 1632 ms 73248 KB Output is correct
6 Correct 2192 ms 125252 KB Output is correct
7 Correct 2288 ms 124736 KB Output is correct
8 Correct 2175 ms 122664 KB Output is correct
9 Correct 50 ms 4716 KB Output is correct
10 Correct 1368 ms 96380 KB Output is correct
11 Correct 1345 ms 96860 KB Output is correct
12 Correct 1551 ms 53152 KB Output is correct
13 Correct 1432 ms 46560 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1271 ms 72676 KB Output is correct
2 Correct 844 ms 90292 KB Output is correct
3 Correct 1426 ms 97892 KB Output is correct
4 Correct 1254 ms 72232 KB Output is correct
5 Correct 48 ms 4716 KB Output is correct
6 Correct 1386 ms 92208 KB Output is correct
7 Correct 1155 ms 64200 KB Output is correct
8 Correct 1046 ms 48624 KB Output is correct
9 Correct 913 ms 40676 KB Output is correct
10 Correct 855 ms 28996 KB Output is correct
11 Correct 911 ms 37968 KB Output is correct
12 Correct 806 ms 27816 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2295 ms 7748 KB Output is correct
2 Correct 48 ms 4716 KB Output is correct
3 Correct 237 ms 5392 KB Output is correct
4 Correct 136 ms 5376 KB Output is correct
5 Correct 1374 ms 7556 KB Output is correct
6 Correct 2331 ms 7472 KB Output is correct
7 Correct 1382 ms 7564 KB Output is correct
8 Correct 1065 ms 6556 KB Output is correct
9 Correct 1047 ms 6600 KB Output is correct
10 Correct 1073 ms 6904 KB Output is correct
11 Correct 1721 ms 7232 KB Output is correct
12 Correct 1716 ms 7304 KB Output is correct
13 Correct 1727 ms 7084 KB Output is correct
14 Correct 1275 ms 7560 KB Output is correct
15 Correct 1360 ms 7480 KB Output is correct
16 Correct 2299 ms 7716 KB Output is correct
17 Correct 2326 ms 7716 KB Output is correct
18 Correct 2294 ms 7772 KB Output is correct
19 Correct 2303 ms 7456 KB Output is correct
20 Correct 1926 ms 7540 KB Output is correct
21 Correct 1916 ms 7280 KB Output is correct
22 Correct 2199 ms 7412 KB Output is correct
23 Correct 1415 ms 7064 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 72960 KB Output is correct
2 Correct 1731 ms 72916 KB Output is correct
3 Correct 1759 ms 73320 KB Output is correct
4 Correct 1675 ms 72868 KB Output is correct
5 Correct 1632 ms 73248 KB Output is correct
6 Correct 2192 ms 125252 KB Output is correct
7 Correct 2288 ms 124736 KB Output is correct
8 Correct 2175 ms 122664 KB Output is correct
9 Correct 50 ms 4716 KB Output is correct
10 Correct 1368 ms 96380 KB Output is correct
11 Correct 1345 ms 96860 KB Output is correct
12 Correct 1551 ms 53152 KB Output is correct
13 Correct 1432 ms 46560 KB Output is correct
14 Correct 1271 ms 72676 KB Output is correct
15 Correct 844 ms 90292 KB Output is correct
16 Correct 1426 ms 97892 KB Output is correct
17 Correct 1254 ms 72232 KB Output is correct
18 Correct 48 ms 4716 KB Output is correct
19 Correct 1386 ms 92208 KB Output is correct
20 Correct 1155 ms 64200 KB Output is correct
21 Correct 1046 ms 48624 KB Output is correct
22 Correct 913 ms 40676 KB Output is correct
23 Correct 855 ms 28996 KB Output is correct
24 Correct 911 ms 37968 KB Output is correct
25 Correct 806 ms 27816 KB Output is correct
26 Correct 1707 ms 73060 KB Output is correct
27 Correct 2058 ms 99904 KB Output is correct
28 Correct 1805 ms 71164 KB Output is correct
29 Correct 1358 ms 28624 KB Output is correct
30 Correct 2032 ms 87636 KB Output is correct
31 Correct 1992 ms 89680 KB Output is correct
32 Correct 2027 ms 90180 KB Output is correct
33 Correct 1745 ms 71432 KB Output is correct
34 Correct 1765 ms 71608 KB Output is correct
35 Correct 1762 ms 71972 KB Output is correct
36 Correct 1403 ms 35468 KB Output is correct
37 Correct 1448 ms 34212 KB Output is correct
38 Correct 1367 ms 32684 KB Output is correct
39 Correct 1248 ms 18852 KB Output is correct
40 Correct 1234 ms 18304 KB Output is correct
41 Correct 1205 ms 17648 KB Output is correct
42 Correct 1154 ms 17224 KB Output is correct
43 Correct 1141 ms 16660 KB Output is correct
44 Correct 1143 ms 16076 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 41 ms 8812 KB Output is correct
4 Correct 7 ms 3180 KB Output is correct
5 Correct 15 ms 4844 KB Output is correct
6 Correct 12 ms 4716 KB Output is correct
7 Correct 16 ms 4716 KB Output is correct
8 Correct 17 ms 4588 KB Output is correct
9 Correct 19 ms 5740 KB Output is correct
10 Correct 18 ms 4716 KB Output is correct
11 Correct 17 ms 4716 KB Output is correct
12 Correct 20 ms 5100 KB Output is correct
13 Correct 25 ms 5612 KB Output is correct
14 Correct 22 ms 5228 KB Output is correct
15 Correct 19 ms 4844 KB Output is correct
16 Correct 20 ms 5100 KB Output is correct
17 Correct 18 ms 5100 KB Output is correct
18 Correct 1751 ms 72960 KB Output is correct
19 Correct 1731 ms 72916 KB Output is correct
20 Correct 1759 ms 73320 KB Output is correct
21 Correct 1675 ms 72868 KB Output is correct
22 Correct 1632 ms 73248 KB Output is correct
23 Correct 2192 ms 125252 KB Output is correct
24 Correct 2288 ms 124736 KB Output is correct
25 Correct 2175 ms 122664 KB Output is correct
26 Correct 50 ms 4716 KB Output is correct
27 Correct 1368 ms 96380 KB Output is correct
28 Correct 1345 ms 96860 KB Output is correct
29 Correct 1551 ms 53152 KB Output is correct
30 Correct 1432 ms 46560 KB Output is correct
31 Correct 1271 ms 72676 KB Output is correct
32 Correct 844 ms 90292 KB Output is correct
33 Correct 1426 ms 97892 KB Output is correct
34 Correct 1254 ms 72232 KB Output is correct
35 Correct 48 ms 4716 KB Output is correct
36 Correct 1386 ms 92208 KB Output is correct
37 Correct 1155 ms 64200 KB Output is correct
38 Correct 1046 ms 48624 KB Output is correct
39 Correct 913 ms 40676 KB Output is correct
40 Correct 855 ms 28996 KB Output is correct
41 Correct 911 ms 37968 KB Output is correct
42 Correct 806 ms 27816 KB Output is correct
43 Correct 2295 ms 7748 KB Output is correct
44 Correct 48 ms 4716 KB Output is correct
45 Correct 237 ms 5392 KB Output is correct
46 Correct 136 ms 5376 KB Output is correct
47 Correct 1374 ms 7556 KB Output is correct
48 Correct 2331 ms 7472 KB Output is correct
49 Correct 1382 ms 7564 KB Output is correct
50 Correct 1065 ms 6556 KB Output is correct
51 Correct 1047 ms 6600 KB Output is correct
52 Correct 1073 ms 6904 KB Output is correct
53 Correct 1721 ms 7232 KB Output is correct
54 Correct 1716 ms 7304 KB Output is correct
55 Correct 1727 ms 7084 KB Output is correct
56 Correct 1275 ms 7560 KB Output is correct
57 Correct 1360 ms 7480 KB Output is correct
58 Correct 2299 ms 7716 KB Output is correct
59 Correct 2326 ms 7716 KB Output is correct
60 Correct 2294 ms 7772 KB Output is correct
61 Correct 2303 ms 7456 KB Output is correct
62 Correct 1926 ms 7540 KB Output is correct
63 Correct 1916 ms 7280 KB Output is correct
64 Correct 2199 ms 7412 KB Output is correct
65 Correct 1415 ms 7064 KB Output is correct
66 Correct 1707 ms 73060 KB Output is correct
67 Correct 2058 ms 99904 KB Output is correct
68 Correct 1805 ms 71164 KB Output is correct
69 Correct 1358 ms 28624 KB Output is correct
70 Correct 2032 ms 87636 KB Output is correct
71 Correct 1992 ms 89680 KB Output is correct
72 Correct 2027 ms 90180 KB Output is correct
73 Correct 1745 ms 71432 KB Output is correct
74 Correct 1765 ms 71608 KB Output is correct
75 Correct 1762 ms 71972 KB Output is correct
76 Correct 1403 ms 35468 KB Output is correct
77 Correct 1448 ms 34212 KB Output is correct
78 Correct 1367 ms 32684 KB Output is correct
79 Correct 1248 ms 18852 KB Output is correct
80 Correct 1234 ms 18304 KB Output is correct
81 Correct 1205 ms 17648 KB Output is correct
82 Correct 1154 ms 17224 KB Output is correct
83 Correct 1141 ms 16660 KB Output is correct
84 Correct 1143 ms 16076 KB Output is correct
85 Correct 2850 ms 74004 KB Output is correct
86 Correct 272 ms 11468 KB Output is correct
87 Correct 189 ms 15864 KB Output is correct
88 Correct 1890 ms 86812 KB Output is correct
89 Correct 2835 ms 72640 KB Output is correct
90 Correct 1872 ms 94460 KB Output is correct
91 Correct 1818 ms 73108 KB Output is correct
92 Correct 1807 ms 72780 KB Output is correct
93 Correct 2382 ms 110064 KB Output is correct
94 Correct 2364 ms 73604 KB Output is correct
95 Correct 2311 ms 73356 KB Output is correct
96 Correct 2562 ms 112820 KB Output is correct
97 Correct 1645 ms 40672 KB Output is correct
98 Correct 1561 ms 37380 KB Output is correct
99 Correct 2873 ms 75008 KB Output is correct
100 Correct 2807 ms 73848 KB Output is correct
101 Correct 2849 ms 73840 KB Output is correct
102 Correct 2833 ms 73820 KB Output is correct
103 Correct 2836 ms 117464 KB Output is correct
104 Correct 2796 ms 117276 KB Output is correct
105 Correct 2260 ms 47016 KB Output is correct
106 Correct 1834 ms 27472 KB Output is correct
107 Correct 2148 ms 53792 KB Output is correct
108 Correct 2792 ms 109392 KB Output is correct
109 Correct 1972 ms 113380 KB Output is correct