oj.uz

Submission #245775

# Submission time Handle Problem Language Result Execution time Memory
245775 2020-07-07T11:15:29 Z icypiggy Bridges (APIO19_bridges) C++14
14 / 100
 972 ms 13664 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
    }
};
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) {
    while(parent[x]!=x) {
        x = parent[x] = parent[parent[x]];
    }
    while(parent[y]!=y) {
        y = parent[y] = parent[parent[y]];
    }
    if(x!=y) {
        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)
    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);
            }
        }
        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]) {
                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;
    const int bucket_size = 500;
    vector<int> breakpoints;
    for(int i=0; i<qc; i++) {
        if(i%bucket_size==0) breakpoints.push_back(q.size());
        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);
        }
    }
    breakpoints.push_back(q.size());
    sort(sorted_edge.begin(), sorted_edge.end());
 
    memset(visited, -1, sizeof(visited));
    for(int i=1; i<breakpoints.size(); i++) {
        //cout << "?\n";
        ans_query(breakpoints[i-1], breakpoints[i]);
    }
    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:149:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<breakpoints.size(); i++) {
                  ~^~~~~~~~~~~~~~~~~~~
bridges.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<output.size(); i++) {
                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 9 ms 4480 KB Output is correct
3 Incorrect 42 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 972 ms 12004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 866 ms 11184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 13420 KB Output is correct
2 Correct 148 ms 8068 KB Output is correct
3 Correct 169 ms 9996 KB Output is correct
4 Correct 172 ms 10088 KB Output is correct
5 Correct 599 ms 13548 KB Output is correct
6 Correct 693 ms 13360 KB Output is correct
7 Correct 581 ms 13476 KB Output is correct
8 Correct 525 ms 10680 KB Output is correct
9 Correct 537 ms 10744 KB Output is correct
10 Correct 515 ms 10856 KB Output is correct
11 Correct 688 ms 12132 KB Output is correct
12 Correct 671 ms 12000 KB Output is correct
13 Correct 648 ms 12256 KB Output is correct
14 Correct 572 ms 13664 KB Output is correct
15 Correct 589 ms 13516 KB Output is correct
16 Correct 722 ms 13280 KB Output is correct
17 Correct 727 ms 13404 KB Output is correct
18 Correct 723 ms 13280 KB Output is correct
19 Correct 750 ms 13408 KB Output is correct
20 Correct 704 ms 12636 KB Output is correct
21 Correct 713 ms 12588 KB Output is correct
22 Correct 719 ms 13412 KB Output is correct
23 Correct 573 ms 12508 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 972 ms 12004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 9 ms 4480 KB Output is correct
3 Incorrect 42 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -