oj.uz

답안 #372895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372895 2021-03-02T08:08:39 Z jainbot27 다리 (APIO19_bridges) C++17
100 / 100
 2368 ms 125212 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 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 34 ms 8812 KB Output is correct
4 Correct 6 ms 3180 KB Output is correct
5 Correct 15 ms 4844 KB Output is correct
6 Correct 13 ms 4716 KB Output is correct
7 Correct 17 ms 4716 KB Output is correct
8 Correct 17 ms 4588 KB Output is correct
9 Correct 22 ms 5740 KB Output is correct
10 Correct 18 ms 4716 KB Output is correct
11 Correct 20 ms 4716 KB Output is correct
12 Correct 21 ms 5100 KB Output is correct
13 Correct 25 ms 5740 KB Output is correct
14 Correct 23 ms 5228 KB Output is correct
15 Correct 19 ms 4844 KB Output is correct
16 Correct 22 ms 5088 KB Output is correct
17 Correct 19 ms 5100 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1538 ms 73032 KB Output is correct
2 Correct 1548 ms 72996 KB Output is correct
3 Correct 1484 ms 73348 KB Output is correct
4 Correct 1461 ms 72988 KB Output is correct
5 Correct 1463 ms 73328 KB Output is correct
6 Correct 2111 ms 125212 KB Output is correct
7 Correct 2114 ms 124668 KB Output is correct
8 Correct 2089 ms 122820 KB Output is correct
9 Correct 56 ms 4792 KB Output is correct
10 Correct 1225 ms 96256 KB Output is correct
11 Correct 1185 ms 96796 KB Output is correct
12 Correct 1313 ms 53204 KB Output is correct
13 Correct 1246 ms 46836 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1164 ms 72632 KB Output is correct
2 Correct 920 ms 90220 KB Output is correct
3 Correct 1375 ms 97892 KB Output is correct
4 Correct 1155 ms 72168 KB Output is correct
5 Correct 48 ms 4716 KB Output is correct
6 Correct 1299 ms 92000 KB Output is correct
7 Correct 1047 ms 64236 KB Output is correct
8 Correct 912 ms 48636 KB Output is correct
9 Correct 790 ms 40712 KB Output is correct
10 Correct 724 ms 29052 KB Output is correct
11 Correct 784 ms 37988 KB Output is correct
12 Correct 695 ms 27748 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1762 ms 7544 KB Output is correct
2 Correct 55 ms 4716 KB Output is correct
3 Correct 194 ms 5408 KB Output is correct
4 Correct 103 ms 5220 KB Output is correct
5 Correct 900 ms 7456 KB Output is correct
6 Correct 1717 ms 7452 KB Output is correct
7 Correct 909 ms 7636 KB Output is correct
8 Correct 856 ms 6608 KB Output is correct
9 Correct 824 ms 6816 KB Output is correct
10 Correct 830 ms 6816 KB Output is correct
11 Correct 1314 ms 7212 KB Output is correct
12 Correct 1313 ms 7168 KB Output is correct
13 Correct 1349 ms 7408 KB Output is correct
14 Correct 811 ms 7476 KB Output is correct
15 Correct 900 ms 7520 KB Output is correct
16 Correct 1779 ms 7460 KB Output is correct
17 Correct 1804 ms 7560 KB Output is correct
18 Correct 1771 ms 7620 KB Output is correct
19 Correct 1788 ms 7492 KB Output is correct
20 Correct 1528 ms 7424 KB Output is correct
21 Correct 1475 ms 7236 KB Output is correct
22 Correct 1711 ms 7976 KB Output is correct
23 Correct 990 ms 7080 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1538 ms 73032 KB Output is correct
2 Correct 1548 ms 72996 KB Output is correct
3 Correct 1484 ms 73348 KB Output is correct
4 Correct 1461 ms 72988 KB Output is correct
5 Correct 1463 ms 73328 KB Output is correct
6 Correct 2111 ms 125212 KB Output is correct
7 Correct 2114 ms 124668 KB Output is correct
8 Correct 2089 ms 122820 KB Output is correct
9 Correct 56 ms 4792 KB Output is correct
10 Correct 1225 ms 96256 KB Output is correct
11 Correct 1185 ms 96796 KB Output is correct
12 Correct 1313 ms 53204 KB Output is correct
13 Correct 1246 ms 46836 KB Output is correct
14 Correct 1164 ms 72632 KB Output is correct
15 Correct 920 ms 90220 KB Output is correct
16 Correct 1375 ms 97892 KB Output is correct
17 Correct 1155 ms 72168 KB Output is correct
18 Correct 48 ms 4716 KB Output is correct
19 Correct 1299 ms 92000 KB Output is correct
20 Correct 1047 ms 64236 KB Output is correct
21 Correct 912 ms 48636 KB Output is correct
22 Correct 790 ms 40712 KB Output is correct
23 Correct 724 ms 29052 KB Output is correct
24 Correct 784 ms 37988 KB Output is correct
25 Correct 695 ms 27748 KB Output is correct
26 Correct 1483 ms 73036 KB Output is correct
27 Correct 1827 ms 100000 KB Output is correct
28 Correct 1563 ms 71480 KB Output is correct
29 Correct 1113 ms 28708 KB Output is correct
30 Correct 1763 ms 87488 KB Output is correct
31 Correct 1746 ms 89704 KB Output is correct
32 Correct 1756 ms 90096 KB Output is correct
33 Correct 1525 ms 71468 KB Output is correct
34 Correct 1557 ms 71688 KB Output is correct
35 Correct 1546 ms 71948 KB Output is correct
36 Correct 1161 ms 35404 KB Output is correct
37 Correct 1175 ms 34176 KB Output is correct
38 Correct 1168 ms 32608 KB Output is correct
39 Correct 964 ms 18872 KB Output is correct
40 Correct 954 ms 18080 KB Output is correct
41 Correct 955 ms 17568 KB Output is correct
42 Correct 931 ms 17300 KB Output is correct
43 Correct 930 ms 16808 KB Output is correct
44 Correct 910 ms 16040 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 34 ms 8812 KB Output is correct
4 Correct 6 ms 3180 KB Output is correct
5 Correct 15 ms 4844 KB Output is correct
6 Correct 13 ms 4716 KB Output is correct
7 Correct 17 ms 4716 KB Output is correct
8 Correct 17 ms 4588 KB Output is correct
9 Correct 22 ms 5740 KB Output is correct
10 Correct 18 ms 4716 KB Output is correct
11 Correct 20 ms 4716 KB Output is correct
12 Correct 21 ms 5100 KB Output is correct
13 Correct 25 ms 5740 KB Output is correct
14 Correct 23 ms 5228 KB Output is correct
15 Correct 19 ms 4844 KB Output is correct
16 Correct 22 ms 5088 KB Output is correct
17 Correct 19 ms 5100 KB Output is correct
18 Correct 1538 ms 73032 KB Output is correct
19 Correct 1548 ms 72996 KB Output is correct
20 Correct 1484 ms 73348 KB Output is correct
21 Correct 1461 ms 72988 KB Output is correct
22 Correct 1463 ms 73328 KB Output is correct
23 Correct 2111 ms 125212 KB Output is correct
24 Correct 2114 ms 124668 KB Output is correct
25 Correct 2089 ms 122820 KB Output is correct
26 Correct 56 ms 4792 KB Output is correct
27 Correct 1225 ms 96256 KB Output is correct
28 Correct 1185 ms 96796 KB Output is correct
29 Correct 1313 ms 53204 KB Output is correct
30 Correct 1246 ms 46836 KB Output is correct
31 Correct 1164 ms 72632 KB Output is correct
32 Correct 920 ms 90220 KB Output is correct
33 Correct 1375 ms 97892 KB Output is correct
34 Correct 1155 ms 72168 KB Output is correct
35 Correct 48 ms 4716 KB Output is correct
36 Correct 1299 ms 92000 KB Output is correct
37 Correct 1047 ms 64236 KB Output is correct
38 Correct 912 ms 48636 KB Output is correct
39 Correct 790 ms 40712 KB Output is correct
40 Correct 724 ms 29052 KB Output is correct
41 Correct 784 ms 37988 KB Output is correct
42 Correct 695 ms 27748 KB Output is correct
43 Correct 1762 ms 7544 KB Output is correct
44 Correct 55 ms 4716 KB Output is correct
45 Correct 194 ms 5408 KB Output is correct
46 Correct 103 ms 5220 KB Output is correct
47 Correct 900 ms 7456 KB Output is correct
48 Correct 1717 ms 7452 KB Output is correct
49 Correct 909 ms 7636 KB Output is correct
50 Correct 856 ms 6608 KB Output is correct
51 Correct 824 ms 6816 KB Output is correct
52 Correct 830 ms 6816 KB Output is correct
53 Correct 1314 ms 7212 KB Output is correct
54 Correct 1313 ms 7168 KB Output is correct
55 Correct 1349 ms 7408 KB Output is correct
56 Correct 811 ms 7476 KB Output is correct
57 Correct 900 ms 7520 KB Output is correct
58 Correct 1779 ms 7460 KB Output is correct
59 Correct 1804 ms 7560 KB Output is correct
60 Correct 1771 ms 7620 KB Output is correct
61 Correct 1788 ms 7492 KB Output is correct
62 Correct 1528 ms 7424 KB Output is correct
63 Correct 1475 ms 7236 KB Output is correct
64 Correct 1711 ms 7976 KB Output is correct
65 Correct 990 ms 7080 KB Output is correct
66 Correct 1483 ms 73036 KB Output is correct
67 Correct 1827 ms 100000 KB Output is correct
68 Correct 1563 ms 71480 KB Output is correct
69 Correct 1113 ms 28708 KB Output is correct
70 Correct 1763 ms 87488 KB Output is correct
71 Correct 1746 ms 89704 KB Output is correct
72 Correct 1756 ms 90096 KB Output is correct
73 Correct 1525 ms 71468 KB Output is correct
74 Correct 1557 ms 71688 KB Output is correct
75 Correct 1546 ms 71948 KB Output is correct
76 Correct 1161 ms 35404 KB Output is correct
77 Correct 1175 ms 34176 KB Output is correct
78 Correct 1168 ms 32608 KB Output is correct
79 Correct 964 ms 18872 KB Output is correct
80 Correct 954 ms 18080 KB Output is correct
81 Correct 955 ms 17568 KB Output is correct
82 Correct 931 ms 17300 KB Output is correct
83 Correct 930 ms 16808 KB Output is correct
84 Correct 910 ms 16040 KB Output is correct
85 Correct 2327 ms 74176 KB Output is correct
86 Correct 233 ms 11512 KB Output is correct
87 Correct 137 ms 15724 KB Output is correct
88 Correct 1398 ms 86800 KB Output is correct
89 Correct 2328 ms 72724 KB Output is correct
90 Correct 1378 ms 94480 KB Output is correct
91 Correct 1623 ms 72980 KB Output is correct
92 Correct 1586 ms 72848 KB Output is correct
93 Correct 2108 ms 109964 KB Output is correct
94 Correct 1898 ms 73564 KB Output is correct
95 Correct 1960 ms 73352 KB Output is correct
96 Correct 2156 ms 113048 KB Output is correct
97 Correct 1063 ms 40628 KB Output is correct
98 Correct 1086 ms 37324 KB Output is correct
99 Correct 2368 ms 75096 KB Output is correct
100 Correct 2322 ms 73856 KB Output is correct
101 Correct 2325 ms 73848 KB Output is correct
102 Correct 2292 ms 73852 KB Output is correct
103 Correct 2363 ms 117220 KB Output is correct
104 Correct 2358 ms 117584 KB Output is correct
105 Correct 1809 ms 47120 KB Output is correct
106 Correct 1457 ms 27596 KB Output is correct
107 Correct 1737 ms 53912 KB Output is correct
108 Correct 2329 ms 109356 KB Output is correct
109 Correct 1615 ms 113260 KB Output is correct