oj.uz

Submission #477979

# Submission time Handle Problem Language Result Execution time Memory
477979 2021-10-04T23:28:37 Z jeroenodb Bridges (APIO19_bridges) C++14
100 / 100
 2538 ms 12896 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct DSU{
    vector<int> szpar;
    int components;
    DSU(int n) {
        szpar.assign(n+1,-1);
        components = n;
    }
    void reset() {
        fill(all(szpar),-1);
        components=szpar.size()-1;
    }
    void link(int a, int b) {
        components--;
        if(szpar[a]>szpar[b]) {
            swap(a,b);
        }
        szpar[a] += szpar[b];
        szpar[b] = a;
    }
    void unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) {
            link(pa,pb);
        }
    }
    int find(int a) {
        if(szpar[a]<0) return a;
        return szpar[a] = find(szpar[a]);
    }
};
struct mys {
    bitset<mxN> vis;
    vi st;
    bool add(int i) {
        if(vis[i]) return true;
        vis[i]=true;
        st.push_back(i);
        return false;
    }
    void reset() {
        for(auto i : st) vis[i]=false;
        st.clear();
    }
};
struct edge{ 
    int a,b,w;
    bool operator<(const edge& o) const {
        return w>o.w;
    }
};
const int B=807;
struct query {
    int t,b,r;
};
edge es[mxN];
struct comp{ bool operator()(int a, int b) const {return es[a]<es[b] or (es[a].w==es[b].w and a<b);} };
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin >> n >> m;
    for(int i=0;i<m;++i) {
        auto& e = es[i];
        cin >> e.a >> e.b >> e.w;
        e.a--,e.b--;
    }
    int Q; cin >> Q;
    
    set<int,comp> order;
    for(int i=0;i<m;++i) order.insert(i);
    DSU dsu(n),dsu2(n);
    mys s,s2,verts;
    vvi adj(n);
    vector<query> qs;
    for(int iter=0;iter<Q;iter+=B) {
        int len = min(B,Q-iter);
        qs.resize(len);
        s.reset();
        for(auto& q : qs) {
            cin >> q.t >> q.b >> q.r;
            q.b--;
            if(q.t==1) {
                s.add(q.b);
            }
        }

        vi rq; rq.reserve(len);
        for(int i=0;i<len;++i) if(qs[i].t==2) rq.push_back(i);
        sort(all(rq), [&](int c,int d){return qs[c].r>qs[d].r;});
        dsu.reset();
        auto it = rq.begin();
        auto it2 = order.begin();
        while(it!=rq.end()) {
            if(it2==order.end() or (it!=rq.end() and qs[*it].r>es[*it2].w)) {
                // do query
                auto add= [&](int a, int b) {
                    a=dsu.find(a), b=dsu.find(b);
                    if(!verts.add(a)) adj[a].clear();
                    if(!verts.add(b)) adj[b].clear();
                    if(a==b) return;
                    adj[a].push_back(b);
                    adj[b].push_back(a);
                };
                s2.reset();
                verts.reset();
                auto& q = qs[*it];
                for(int j=*it-1;j>=0;--j) {
                    if(qs[j].t==1 and !s2.vis[qs[j].b]) {
                        s2.add(qs[j].b);
                        auto& e = es[qs[j].b];
                        if(qs[j].r>=q.r) add(e.a,e.b);
                    }
                }
                
                for(auto i:s.st) {
                    if(!s2.vis[i]) {
                        auto& e = es[i];
                        if(e.w>=q.r) add(e.a,e.b);
                    }
                }
                int mycomp = dsu.find(q.b);
                vi st; st.push_back(mycomp);
                add(mycomp,mycomp);
                verts.reset();
                verts.add(mycomp);
                q.b=0;
                while(!st.empty()) {
                    int at = st.back(); st.pop_back();
                    q.b+=-dsu.szpar[at];
                    for(int to : adj[at]) if(!verts.vis[to]) {
                        verts.add(to);
                        st.push_back(to);
                    }
                }
                ++it;
            } else {
                auto& e = es[*it2];
                if(!s.vis[*it2]) dsu.unite(e.a,e.b);
                ++it2;
            }
        }
        for(auto& q : qs) {
            if(q.t==1) {
                order.erase(q.b);
                es[q.b].w = q.r;
                order.insert(q.b);
            } else {
                cout << q.b << '\n';
            }
        }
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 38 ms 436 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 27 ms 332 KB Output is correct
6 Correct 24 ms 388 KB Output is correct
7 Correct 35 ms 388 KB Output is correct
8 Correct 29 ms 380 KB Output is correct
9 Correct 40 ms 380 KB Output is correct
10 Correct 36 ms 388 KB Output is correct
11 Correct 29 ms 376 KB Output is correct
12 Correct 37 ms 388 KB Output is correct
13 Correct 40 ms 404 KB Output is correct
14 Correct 36 ms 516 KB Output is correct
15 Correct 32 ms 504 KB Output is correct
16 Correct 36 ms 376 KB Output is correct
17 Correct 33 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1733 ms 6204 KB Output is correct
2 Correct 1540 ms 6280 KB Output is correct
3 Correct 1604 ms 6424 KB Output is correct
4 Correct 1532 ms 6560 KB Output is correct
5 Correct 1569 ms 6216 KB Output is correct
6 Correct 2538 ms 5656 KB Output is correct
7 Correct 2341 ms 5556 KB Output is correct
8 Correct 2248 ms 5488 KB Output is correct
9 Correct 100 ms 452 KB Output is correct
10 Correct 1666 ms 6360 KB Output is correct
11 Correct 1560 ms 6328 KB Output is correct
12 Correct 1117 ms 5556 KB Output is correct
13 Correct 1178 ms 5432 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 4584 KB Output is correct
2 Correct 1219 ms 1600 KB Output is correct
3 Correct 1523 ms 4608 KB Output is correct
4 Correct 1162 ms 4532 KB Output is correct
5 Correct 71 ms 432 KB Output is correct
6 Correct 1349 ms 4352 KB Output is correct
7 Correct 1065 ms 4292 KB Output is correct
8 Correct 901 ms 4292 KB Output is correct
9 Correct 690 ms 3940 KB Output is correct
10 Correct 617 ms 3896 KB Output is correct
11 Correct 728 ms 4276 KB Output is correct
12 Correct 624 ms 4420 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 8176 KB Output is correct
2 Correct 75 ms 524 KB Output is correct
3 Correct 162 ms 6220 KB Output is correct
4 Correct 75 ms 6212 KB Output is correct
5 Correct 768 ms 8320 KB Output is correct
6 Correct 1290 ms 8244 KB Output is correct
7 Correct 780 ms 8428 KB Output is correct
8 Correct 571 ms 5144 KB Output is correct
9 Correct 563 ms 5344 KB Output is correct
10 Correct 550 ms 5160 KB Output is correct
11 Correct 959 ms 6592 KB Output is correct
12 Correct 983 ms 6776 KB Output is correct
13 Correct 941 ms 7012 KB Output is correct
14 Correct 630 ms 8564 KB Output is correct
15 Correct 687 ms 8204 KB Output is correct
16 Correct 1363 ms 8212 KB Output is correct
17 Correct 1369 ms 8240 KB Output is correct
18 Correct 1408 ms 8308 KB Output is correct
19 Correct 1356 ms 8032 KB Output is correct
20 Correct 1136 ms 7516 KB Output is correct
21 Correct 1124 ms 7408 KB Output is correct
22 Correct 1261 ms 8216 KB Output is correct
23 Correct 893 ms 7020 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1733 ms 6204 KB Output is correct
2 Correct 1540 ms 6280 KB Output is correct
3 Correct 1604 ms 6424 KB Output is correct
4 Correct 1532 ms 6560 KB Output is correct
5 Correct 1569 ms 6216 KB Output is correct
6 Correct 2538 ms 5656 KB Output is correct
7 Correct 2341 ms 5556 KB Output is correct
8 Correct 2248 ms 5488 KB Output is correct
9 Correct 100 ms 452 KB Output is correct
10 Correct 1666 ms 6360 KB Output is correct
11 Correct 1560 ms 6328 KB Output is correct
12 Correct 1117 ms 5556 KB Output is correct
13 Correct 1178 ms 5432 KB Output is correct
14 Correct 1210 ms 4584 KB Output is correct
15 Correct 1219 ms 1600 KB Output is correct
16 Correct 1523 ms 4608 KB Output is correct
17 Correct 1162 ms 4532 KB Output is correct
18 Correct 71 ms 432 KB Output is correct
19 Correct 1349 ms 4352 KB Output is correct
20 Correct 1065 ms 4292 KB Output is correct
21 Correct 901 ms 4292 KB Output is correct
22 Correct 690 ms 3940 KB Output is correct
23 Correct 617 ms 3896 KB Output is correct
24 Correct 728 ms 4276 KB Output is correct
25 Correct 624 ms 4420 KB Output is correct
26 Correct 1356 ms 6132 KB Output is correct
27 Correct 1841 ms 6416 KB Output is correct
28 Correct 1544 ms 6440 KB Output is correct
29 Correct 1020 ms 6440 KB Output is correct
30 Correct 1840 ms 6428 KB Output is correct
31 Correct 1859 ms 6468 KB Output is correct
32 Correct 1927 ms 6480 KB Output is correct
33 Correct 1493 ms 6196 KB Output is correct
34 Correct 1517 ms 6432 KB Output is correct
35 Correct 1524 ms 6212 KB Output is correct
36 Correct 1137 ms 6268 KB Output is correct
37 Correct 1112 ms 6336 KB Output is correct
38 Correct 1146 ms 6336 KB Output is correct
39 Correct 767 ms 5672 KB Output is correct
40 Correct 774 ms 5592 KB Output is correct
41 Correct 757 ms 5620 KB Output is correct
42 Correct 822 ms 6400 KB Output is correct
43 Correct 851 ms 6448 KB Output is correct
44 Correct 785 ms 6316 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 38 ms 436 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 27 ms 332 KB Output is correct
6 Correct 24 ms 388 KB Output is correct
7 Correct 35 ms 388 KB Output is correct
8 Correct 29 ms 380 KB Output is correct
9 Correct 40 ms 380 KB Output is correct
10 Correct 36 ms 388 KB Output is correct
11 Correct 29 ms 376 KB Output is correct
12 Correct 37 ms 388 KB Output is correct
13 Correct 40 ms 404 KB Output is correct
14 Correct 36 ms 516 KB Output is correct
15 Correct 32 ms 504 KB Output is correct
16 Correct 36 ms 376 KB Output is correct
17 Correct 33 ms 384 KB Output is correct
18 Correct 1733 ms 6204 KB Output is correct
19 Correct 1540 ms 6280 KB Output is correct
20 Correct 1604 ms 6424 KB Output is correct
21 Correct 1532 ms 6560 KB Output is correct
22 Correct 1569 ms 6216 KB Output is correct
23 Correct 2538 ms 5656 KB Output is correct
24 Correct 2341 ms 5556 KB Output is correct
25 Correct 2248 ms 5488 KB Output is correct
26 Correct 100 ms 452 KB Output is correct
27 Correct 1666 ms 6360 KB Output is correct
28 Correct 1560 ms 6328 KB Output is correct
29 Correct 1117 ms 5556 KB Output is correct
30 Correct 1178 ms 5432 KB Output is correct
31 Correct 1210 ms 4584 KB Output is correct
32 Correct 1219 ms 1600 KB Output is correct
33 Correct 1523 ms 4608 KB Output is correct
34 Correct 1162 ms 4532 KB Output is correct
35 Correct 71 ms 432 KB Output is correct
36 Correct 1349 ms 4352 KB Output is correct
37 Correct 1065 ms 4292 KB Output is correct
38 Correct 901 ms 4292 KB Output is correct
39 Correct 690 ms 3940 KB Output is correct
40 Correct 617 ms 3896 KB Output is correct
41 Correct 728 ms 4276 KB Output is correct
42 Correct 624 ms 4420 KB Output is correct
43 Correct 1273 ms 8176 KB Output is correct
44 Correct 75 ms 524 KB Output is correct
45 Correct 162 ms 6220 KB Output is correct
46 Correct 75 ms 6212 KB Output is correct
47 Correct 768 ms 8320 KB Output is correct
48 Correct 1290 ms 8244 KB Output is correct
49 Correct 780 ms 8428 KB Output is correct
50 Correct 571 ms 5144 KB Output is correct
51 Correct 563 ms 5344 KB Output is correct
52 Correct 550 ms 5160 KB Output is correct
53 Correct 959 ms 6592 KB Output is correct
54 Correct 983 ms 6776 KB Output is correct
55 Correct 941 ms 7012 KB Output is correct
56 Correct 630 ms 8564 KB Output is correct
57 Correct 687 ms 8204 KB Output is correct
58 Correct 1363 ms 8212 KB Output is correct
59 Correct 1369 ms 8240 KB Output is correct
60 Correct 1408 ms 8308 KB Output is correct
61 Correct 1356 ms 8032 KB Output is correct
62 Correct 1136 ms 7516 KB Output is correct
63 Correct 1124 ms 7408 KB Output is correct
64 Correct 1261 ms 8216 KB Output is correct
65 Correct 893 ms 7020 KB Output is correct
66 Correct 1356 ms 6132 KB Output is correct
67 Correct 1841 ms 6416 KB Output is correct
68 Correct 1544 ms 6440 KB Output is correct
69 Correct 1020 ms 6440 KB Output is correct
70 Correct 1840 ms 6428 KB Output is correct
71 Correct 1859 ms 6468 KB Output is correct
72 Correct 1927 ms 6480 KB Output is correct
73 Correct 1493 ms 6196 KB Output is correct
74 Correct 1517 ms 6432 KB Output is correct
75 Correct 1524 ms 6212 KB Output is correct
76 Correct 1137 ms 6268 KB Output is correct
77 Correct 1112 ms 6336 KB Output is correct
78 Correct 1146 ms 6336 KB Output is correct
79 Correct 767 ms 5672 KB Output is correct
80 Correct 774 ms 5592 KB Output is correct
81 Correct 757 ms 5620 KB Output is correct
82 Correct 822 ms 6400 KB Output is correct
83 Correct 851 ms 6448 KB Output is correct
84 Correct 785 ms 6316 KB Output is correct
85 Correct 2124 ms 9120 KB Output is correct
86 Correct 239 ms 6352 KB Output is correct
87 Correct 140 ms 6236 KB Output is correct
88 Correct 1446 ms 8704 KB Output is correct
89 Correct 2145 ms 9420 KB Output is correct
90 Correct 1449 ms 8632 KB Output is correct
91 Correct 1583 ms 6308 KB Output is correct
92 Correct 1647 ms 6360 KB Output is correct
93 Correct 2200 ms 5500 KB Output is correct
94 Correct 1767 ms 7636 KB Output is correct
95 Correct 1848 ms 7772 KB Output is correct
96 Correct 1798 ms 6752 KB Output is correct
97 Correct 1055 ms 8404 KB Output is correct
98 Correct 1114 ms 8512 KB Output is correct
99 Correct 2141 ms 9016 KB Output is correct
100 Correct 2049 ms 12780 KB Output is correct
101 Correct 2181 ms 12872 KB Output is correct
102 Correct 2086 ms 12896 KB Output is correct
103 Correct 1764 ms 10536 KB Output is correct
104 Correct 1780 ms 10348 KB Output is correct
105 Correct 1350 ms 10196 KB Output is correct
106 Correct 1128 ms 9544 KB Output is correct
107 Correct 1265 ms 10576 KB Output is correct
108 Correct 1890 ms 11636 KB Output is correct
109 Correct 1474 ms 9024 KB Output is correct