Submission #237316

#	Time	Username	Problem	Language	Result	Execution time	Memory
237316		jhnah917	Bridges (APIO19_bridges)	C++14	43 / 100	150 ms	17640 KiB

bridges

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct Edge{
    int s, e, x, i;
    Edge(int s, int e, int x, int i) : s(s), e(e), x(x), i(i) {}
    Edge() : Edge(0, 0, 0, 0) {}
    bool operator < (const Edge &t) const {
        return i < t.i;
    }
};
struct Query{
    int a, b, i, k;
    Query(int a, int b, int i, int k) : a(a), b(b), i(i), k(k) {}
    Query() : Query(0, 0, 0, 0) {}
    bool operator < (const Query &t) const {
        if(b != t.b) return b < t.b;
        return k < t.k;
    }
    bool operator > (const Query &t) const {
        if(b != t.b) return b > t.b;
        return k < t.k;
    }
};

int n, m, q;
vector<Edge> g[50505];
Edge edge[101010]{};

void subtask1(){
    set<Edge> st[1010];
    int chk[1010] = {0};
    for(int i=1; i<=n; i++) st[i] = set<Edge>(all(g[i]));
    while(q--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1){
            Edge &now = edge[a];
            st[now.s].erase(st[now.s].lower_bound(Edge(-1, -1, -1, a)));
            st[now.e].erase(st[now.e].lower_bound(Edge(-1, -1, -1, a)));
            now.x = b;
            st[now.s].insert(now);
            st[now.e].emplace(now.e, now.s, now.x, now.i);
        }else{
            memset(chk, 0, sizeof chk);
            queue<int> que; que.push(a); chk[a] = 1;
            int ans = 0;
            while(!que.empty()){
                int now = que.front(); que.pop();
                ans++;
                for(auto i : st[now]){
                    if(chk[i.e]) continue;
                    if(i.x < b) continue;
                    chk[i.e] = 1;
                    que.push(i.e);
                }
            }
            cout << ans << "\n";
        }
    }
}

const int sz = 1u << 17u;
struct Sub2_Seg{
    int tree[1 << 18];
    Sub2_Seg(){ memset(tree, 0x3f, sizeof tree); }
    void update(int x, int v, int node = 1, int s = 1, int e = n-1){
        if(s == e){ tree[node] = v; return; }
        int m = s + e >> 1;
        if(x <= m) update(x, v, node << 1, s, m);
        else update(x, v, node << 1 | 1, m+1, e);
        tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
    }
    int queryL(int x, int v, int node = 1, int s = 1, int e = n-1){
        if(x < s) return 0;
        if(s == e){
            if(tree[node] >= v) return 0;
            return s;
        }
        if(e <= x && tree[node] >= v) return 0;
        int m = s + e >> 1;
        int t = queryL(x, v, node << 1 | 1, m+1, e);
        if(t) return t;
        return queryL(x, v, node << 1, s, m);
    }
    int queryR(int x, int v, int node = 1, int s = 1, int e = n-1){
        if(e < x) return n;
        if(s == e){
            if(tree[node] >= v) return n;
            return s;
        }
        if(x <= s && tree[node] >= v) return n;
        int m = s + e >> 1;
        int t = queryR(x, v, node << 1, s, m);
        if(t != n) return t;
        return queryR(x, v, node << 1 | 1, m+1, e);
    }
};

void subtask2(){
    Sub2_Seg seg;
    for(int i=1; i<n; i++){
        seg.update(i, edge[i].x);
    }
    while(q--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) seg.update(a, b);
        else {
            cout << seg.queryR(a, b) - seg.queryL(a-1, b) << "\n";
        }
    }
}

struct Sub4_UF{
    int par[101010]{};
    int sz[101010]{};
    Sub4_UF(){
        iota(par, par+101010, 0);
        fill(sz+1, sz+n+1, 1);
    }
    int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
    void merge(int u, int v){
        u = find(u), v = find(v);
        if(u ^ v) par[u] = v, sz[v] += sz[u];
    }
};

void subtask4(){
    Sub4_UF uf;
    int ans[101010] = {0};
    vector<Query> qry;
    for(int i=1; i<=q; i++){
        int op, a, b; cin >> op >> a >> b;
        qry.emplace_back(a, b, i, 1);
    }
    for(int i=1; i<=m; i++){
        qry.emplace_back(0, edge[i].x, i, 0);
    }
    sort(all(qry), greater<>());
    for(auto i : qry){
        if(i.k == 0) uf.merge(edge[i.i].s, edge[i.i].e);
        else ans[i.i] = uf.sz[uf.find(i.a)];
    }
    for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    bool is_2 = true;
    cin >> n >> m;
    if(m != n-1) is_2 = false;
    for(int i=0; i<m; i++){
        int s, e, x; cin >> s >> e >> x;
        g[s].emplace_back(s, e, x, i+1);
        g[e].emplace_back(e, s, x, i+1);
        edge[i+1] = {s, e, x, i+1};
        if(s != i+1 && e != i+2) is_2 = false;
    }
    cin >> q;
    if(n <= 1000 && m <= 1000 && q <= 10000){
        subtask1(); return 0;
    }
    if(is_2){
        subtask2(); return 0;
    }
    subtask4();
}

Compilation message (stderr)

bridges.cpp: In member function 'void Sub2_Seg::update(int, int, int, int, int)':
bridges.cpp:75:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s + e >> 1;
                 ~~^~~
bridges.cpp: In member function 'int Sub2_Seg::queryL(int, int, int, int, int)':
bridges.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s + e >> 1;
                 ~~^~~
bridges.cpp: In member function 'int Sub2_Seg::queryR(int, int, int, int, int)':
bridges.cpp:99:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s + e >> 1;
                 ~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27