oj.uz

Submission #245757

# Submission time Handle Problem Language Result Execution time Memory
245757 2020-07-07T10:54:13 Z icypiggy Bridges (APIO19_bridges) C++14
100 / 100
 2338 ms 19300 KB 
#include <bits/stdc++.h>
 
using namespace std;
int n,m,qc;
const int n_max = 5e4+10;
const int m_max = 1e5+10;
const int q_max = 1e5+10;
struct edge {
    int u,v,w,s,e;
    edge() : u(0), v(0), w(0), s(0), e(0) {}
    edge(int _u, int _v, int _w, int _s, int _e) : u(_u), v(_v), w(_w), s(_s), e(_e) {}
    bool operator < (edge other) const {
        return w > other.w; // invert comparator
    }
    void print() {
        //cout << "u: " << u << " v: " << v << " w: " << w << " s: " << s << " e: " << e << "\n";
    }
};
struct query {
    int time, start, weight, ans;
    query() : time(0), start(0), weight(0), ans(0) {}
    query(int _t, int _s, int _w) : time(_t), start(_s), weight(_w), ans(0) {}
    bool operator < (query other) const {
        return weight > other.weight;
    }
};
vector<query> q;
vector<edge> init[m_max];
vector<edge> sorted_edge;
int visited[n_max];
int parent[n_max];
int sz[n_max];
// reset the ufds
void reset_ufds() {
    for(int i=0; i<n_max; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}
int findset(int x) {
    while(parent[x]!=x) {
        x = parent[x] = parent[parent[x]];
    }
    return x;
}
void onion(int x, int y) {
    x = findset(x);
    y = findset(y);
    if(x!=y) {
        //cout << "onion: " << x << " " << y << "\n";
        if(sz[x]>sz[y]) swap(x,y);
        sz[y] += sz[x];
        parent[x] = y;
    }
}
vector<int> adj[n_max];
vector<pair<int,int>> output;
void ans_query(int first, int last) { // [first,last)
    for(int i=0; i<n_max; i++) {
        adj[i].clear();
    }
    if(first>=last) return;
    reset_ufds();
    int ts = q[first].time;
    int te = q[last-1].time;
    sort(q.begin()+first, q.begin()+last); // sort by weight
    auto it = sorted_edge.begin();
    vector<edge> templist;
    for(int i=first; i<last; i++) {
        //cout << "i: " << i << "\n";
        //cout << q[i].time << " " << q[i].weight << "\n";
        while(it!=sorted_edge.end() && it->w >= q[i].weight) {
            //it->print();
            //cout << "weight: " << it->w << " " << it->s << " " << it->e << "\n";
            if(it->s < ts && it->e > te) {
                onion(it->u, it->v);
            } else if((it->s < te && it->s > ts) || (it->e < te && it->e > ts)) {
                // add it to the list of edges to process
                //cout << "templist: " << it->u << " " << it->v << "\n";
                templist.push_back(*it);
            }
            it++;
        }
        int starting = findset(q[i].start);
        int ans = sz[starting];
        for(edge &e: templist) {
            e.u = findset(e.u);
            e.v = findset(e.v);
            adj[e.u].clear();
            adj[e.v].clear();
        }
        for(edge &e: templist) {
            if(e.s < q[i].time && e.e>q[i].time) {
                adj[e.u].push_back(e.v);
                adj[e.v].push_back(e.u);
                //cout << "pushed: ";
                e.print();
            }
        }
        visited[starting] = i; // record the visited time
        //cout << "starting: " << starting << "\n";
        queue<int> bfs;
        bfs.push(starting);
        while(!bfs.empty()) {
            int next = bfs.front();
            //cout << "bfs: " << next << "\n";
            bfs.pop();
            for(int z: adj[next]) {
                z = findset(z);
                if(visited[z]!=i) {
                    visited[z] = i;
                    ans += sz[z];
                    bfs.push(z);
                }
            }
        }
        output.push_back(make_pair(q[i].time, ans));
        //cout << "output: " << q[i].time << " " << ans << "\n";
    }
}
int main() {
    //freopen("../q2/05","r",stdin);
    //freopen("05b","w",stdout);
    cin>>n>>m;
    for(int i=0; i<m; i++) {
        edge e;
        cin >> e.u >> e.v >> e.w;
        e.s = -1;
        e.e = 2e5;
        init[i].push_back(e);
    }
    cin >> qc;
    for(int i=0; i<qc; i++) {
        int a,b,c; cin>>a>>b>>c;
        if(a==2) {
            q.push_back(query(i, b, c));
        } else {
            assert(a==1);
            init[b-1].back().e = i;
            init[b-1].push_back(edge(init[b-1][0].u, init[b-1][0].v, c, i, 2e5));
        }
    }
    for(int i=0; i<m; i++) {
        for(edge e: init[i]) {
            sorted_edge.push_back(e);
        }
    }
    sort(sorted_edge.begin(), sorted_edge.end());
 
    memset(visited, -1, sizeof(visited));
    const int bucket_size = 300;
    for(int i=0; i<bucket_size+q.size(); i+=bucket_size) {
        //cout << i << "????" << i+bucket_size << "\n";
        ans_query(i, min((int) q.size(), i+bucket_size));
    }
    //ans_query(0, q.size());
    sort(output.begin(), output.end());
    for(int i=1; i<output.size(); i++) {
        assert(output[i].first != output[i-1].first);
    }
    for(auto p: output) {
        cout << p.second << "\n";
    }
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<bucket_size+q.size(); i+=bucket_size) {
                  ~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<output.size(); i++) {
                  ~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4480 KB Output is correct
2 Correct 9 ms 4480 KB Output is correct
3 Correct 58 ms 5240 KB Output is correct
4 Correct 24 ms 4988 KB Output is correct
5 Correct 39 ms 5120 KB Output is correct
6 Correct 36 ms 5120 KB Output is correct
7 Correct 36 ms 4992 KB Output is correct
8 Correct 35 ms 5120 KB Output is correct
9 Correct 47 ms 5112 KB Output is correct
10 Correct 36 ms 5120 KB Output is correct
11 Correct 37 ms 5120 KB Output is correct
12 Correct 39 ms 5120 KB Output is correct
13 Correct 41 ms 5108 KB Output is correct
14 Correct 39 ms 5108 KB Output is correct
15 Correct 38 ms 5096 KB Output is correct
16 Correct 39 ms 4992 KB Output is correct
17 Correct 37 ms 4992 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 14800 KB Output is correct
2 Correct 941 ms 14812 KB Output is correct
3 Correct 939 ms 14692 KB Output is correct
4 Correct 921 ms 14684 KB Output is correct
5 Correct 1006 ms 14692 KB Output is correct
6 Correct 1596 ms 14172 KB Output is correct
7 Correct 1428 ms 14284 KB Output is correct
8 Correct 1345 ms 14344 KB Output is correct
9 Correct 179 ms 9316 KB Output is correct
10 Correct 1100 ms 13564 KB Output is correct
11 Correct 1046 ms 13620 KB Output is correct
12 Correct 771 ms 13772 KB Output is correct
13 Correct 2338 ms 16348 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 13316 KB Output is correct
2 Correct 835 ms 11000 KB Output is correct
3 Correct 1090 ms 13116 KB Output is correct
4 Correct 873 ms 13224 KB Output is correct
5 Correct 197 ms 9424 KB Output is correct
6 Correct 948 ms 13024 KB Output is correct
7 Correct 796 ms 13120 KB Output is correct
8 Correct 694 ms 13104 KB Output is correct
9 Correct 600 ms 12464 KB Output is correct
10 Correct 590 ms 12512 KB Output is correct
11 Correct 1555 ms 14692 KB Output is correct
12 Correct 1006 ms 14564 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 17376 KB Output is correct
2 Correct 180 ms 9316 KB Output is correct
3 Correct 186 ms 11748 KB Output is correct
4 Correct 178 ms 11876 KB Output is correct
5 Correct 838 ms 15740 KB Output is correct
6 Correct 947 ms 17248 KB Output is correct
7 Correct 882 ms 15848 KB Output is correct
8 Correct 723 ms 13412 KB Output is correct
9 Correct 711 ms 13416 KB Output is correct
10 Correct 714 ms 13284 KB Output is correct
11 Correct 988 ms 15072 KB Output is correct
12 Correct 950 ms 15200 KB Output is correct
13 Correct 947 ms 15208 KB Output is correct
14 Correct 846 ms 15804 KB Output is correct
15 Correct 856 ms 15756 KB Output is correct
16 Correct 1038 ms 16968 KB Output is correct
17 Correct 1107 ms 16988 KB Output is correct
18 Correct 1037 ms 17144 KB Output is correct
19 Correct 1054 ms 17100 KB Output is correct
20 Correct 1067 ms 15888 KB Output is correct
21 Correct 1016 ms 15812 KB Output is correct
22 Correct 1016 ms 16864 KB Output is correct
23 Correct 852 ms 14556 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 14800 KB Output is correct
2 Correct 941 ms 14812 KB Output is correct
3 Correct 939 ms 14692 KB Output is correct
4 Correct 921 ms 14684 KB Output is correct
5 Correct 1006 ms 14692 KB Output is correct
6 Correct 1596 ms 14172 KB Output is correct
7 Correct 1428 ms 14284 KB Output is correct
8 Correct 1345 ms 14344 KB Output is correct
9 Correct 179 ms 9316 KB Output is correct
10 Correct 1100 ms 13564 KB Output is correct
11 Correct 1046 ms 13620 KB Output is correct
12 Correct 771 ms 13772 KB Output is correct
13 Correct 2338 ms 16348 KB Output is correct
14 Correct 883 ms 13316 KB Output is correct
15 Correct 835 ms 11000 KB Output is correct
16 Correct 1090 ms 13116 KB Output is correct
17 Correct 873 ms 13224 KB Output is correct
18 Correct 197 ms 9424 KB Output is correct
19 Correct 948 ms 13024 KB Output is correct
20 Correct 796 ms 13120 KB Output is correct
21 Correct 694 ms 13104 KB Output is correct
22 Correct 600 ms 12464 KB Output is correct
23 Correct 590 ms 12512 KB Output is correct
24 Correct 1555 ms 14692 KB Output is correct
25 Correct 1006 ms 14564 KB Output is correct
26 Correct 1086 ms 14776 KB Output is correct
27 Correct 1176 ms 14508 KB Output is correct
28 Correct 1014 ms 14820 KB Output is correct
29 Correct 736 ms 14692 KB Output is correct
30 Correct 1244 ms 14536 KB Output is correct
31 Correct 1229 ms 14804 KB Output is correct
32 Correct 1233 ms 14660 KB Output is correct
33 Correct 1067 ms 14792 KB Output is correct
34 Correct 1031 ms 14824 KB Output is correct
35 Correct 1068 ms 14940 KB Output is correct
36 Correct 822 ms 14692 KB Output is correct
37 Correct 816 ms 14556 KB Output is correct
38 Correct 823 ms 14672 KB Output is correct
39 Correct 799 ms 13784 KB Output is correct
40 Correct 787 ms 13744 KB Output is correct
41 Correct 835 ms 13724 KB Output is correct
42 Correct 758 ms 16456 KB Output is correct
43 Correct 716 ms 16332 KB Output is correct
44 Correct 712 ms 16356 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4480 KB Output is correct
2 Correct 9 ms 4480 KB Output is correct
3 Correct 58 ms 5240 KB Output is correct
4 Correct 24 ms 4988 KB Output is correct
5 Correct 39 ms 5120 KB Output is correct
6 Correct 36 ms 5120 KB Output is correct
7 Correct 36 ms 4992 KB Output is correct
8 Correct 35 ms 5120 KB Output is correct
9 Correct 47 ms 5112 KB Output is correct
10 Correct 36 ms 5120 KB Output is correct
11 Correct 37 ms 5120 KB Output is correct
12 Correct 39 ms 5120 KB Output is correct
13 Correct 41 ms 5108 KB Output is correct
14 Correct 39 ms 5108 KB Output is correct
15 Correct 38 ms 5096 KB Output is correct
16 Correct 39 ms 4992 KB Output is correct
17 Correct 37 ms 4992 KB Output is correct
18 Correct 971 ms 14800 KB Output is correct
19 Correct 941 ms 14812 KB Output is correct
20 Correct 939 ms 14692 KB Output is correct
21 Correct 921 ms 14684 KB Output is correct
22 Correct 1006 ms 14692 KB Output is correct
23 Correct 1596 ms 14172 KB Output is correct
24 Correct 1428 ms 14284 KB Output is correct
25 Correct 1345 ms 14344 KB Output is correct
26 Correct 179 ms 9316 KB Output is correct
27 Correct 1100 ms 13564 KB Output is correct
28 Correct 1046 ms 13620 KB Output is correct
29 Correct 771 ms 13772 KB Output is correct
30 Correct 2338 ms 16348 KB Output is correct
31 Correct 883 ms 13316 KB Output is correct
32 Correct 835 ms 11000 KB Output is correct
33 Correct 1090 ms 13116 KB Output is correct
34 Correct 873 ms 13224 KB Output is correct
35 Correct 197 ms 9424 KB Output is correct
36 Correct 948 ms 13024 KB Output is correct
37 Correct 796 ms 13120 KB Output is correct
38 Correct 694 ms 13104 KB Output is correct
39 Correct 600 ms 12464 KB Output is correct
40 Correct 590 ms 12512 KB Output is correct
41 Correct 1555 ms 14692 KB Output is correct
42 Correct 1006 ms 14564 KB Output is correct
43 Correct 969 ms 17376 KB Output is correct
44 Correct 180 ms 9316 KB Output is correct
45 Correct 186 ms 11748 KB Output is correct
46 Correct 178 ms 11876 KB Output is correct
47 Correct 838 ms 15740 KB Output is correct
48 Correct 947 ms 17248 KB Output is correct
49 Correct 882 ms 15848 KB Output is correct
50 Correct 723 ms 13412 KB Output is correct
51 Correct 711 ms 13416 KB Output is correct
52 Correct 714 ms 13284 KB Output is correct
53 Correct 988 ms 15072 KB Output is correct
54 Correct 950 ms 15200 KB Output is correct
55 Correct 947 ms 15208 KB Output is correct
56 Correct 846 ms 15804 KB Output is correct
57 Correct 856 ms 15756 KB Output is correct
58 Correct 1038 ms 16968 KB Output is correct
59 Correct 1107 ms 16988 KB Output is correct
60 Correct 1037 ms 17144 KB Output is correct
61 Correct 1054 ms 17100 KB Output is correct
62 Correct 1067 ms 15888 KB Output is correct
63 Correct 1016 ms 15812 KB Output is correct
64 Correct 1016 ms 16864 KB Output is correct
65 Correct 852 ms 14556 KB Output is correct
66 Correct 1086 ms 14776 KB Output is correct
67 Correct 1176 ms 14508 KB Output is correct
68 Correct 1014 ms 14820 KB Output is correct
69 Correct 736 ms 14692 KB Output is correct
70 Correct 1244 ms 14536 KB Output is correct
71 Correct 1229 ms 14804 KB Output is correct
72 Correct 1233 ms 14660 KB Output is correct
73 Correct 1067 ms 14792 KB Output is correct
74 Correct 1031 ms 14824 KB Output is correct
75 Correct 1068 ms 14940 KB Output is correct
76 Correct 822 ms 14692 KB Output is correct
77 Correct 816 ms 14556 KB Output is correct
78 Correct 823 ms 14672 KB Output is correct
79 Correct 799 ms 13784 KB Output is correct
80 Correct 787 ms 13744 KB Output is correct
81 Correct 835 ms 13724 KB Output is correct
82 Correct 758 ms 16456 KB Output is correct
83 Correct 716 ms 16332 KB Output is correct
84 Correct 712 ms 16356 KB Output is correct
85 Correct 1074 ms 19084 KB Output is correct
86 Correct 205 ms 12028 KB Output is correct
87 Correct 224 ms 12160 KB Output is correct
88 Correct 1062 ms 17624 KB Output is correct
89 Correct 1067 ms 19172 KB Output is correct
90 Correct 1024 ms 17480 KB Output is correct
91 Correct 1030 ms 14640 KB Output is correct
92 Correct 1050 ms 14908 KB Output is correct
93 Correct 1368 ms 14112 KB Output is correct
94 Correct 1089 ms 16560 KB Output is correct
95 Correct 1114 ms 16832 KB Output is correct
96 Correct 1202 ms 16136 KB Output is correct
97 Correct 879 ms 16012 KB Output is correct
98 Correct 1084 ms 18016 KB Output is correct
99 Correct 1093 ms 19044 KB Output is correct
100 Correct 1087 ms 19040 KB Output is correct
101 Correct 1165 ms 19172 KB Output is correct
102 Correct 1114 ms 19300 KB Output is correct
103 Correct 1239 ms 17888 KB Output is correct
104 Correct 1227 ms 17864 KB Output is correct
105 Correct 1382 ms 18784 KB Output is correct
106 Correct 1479 ms 17960 KB Output is correct
107 Correct 1067 ms 16348 KB Output is correct
108 Correct 1217 ms 18660 KB Output is correct
109 Correct 1123 ms 15324 KB Output is correct