Submission #237310

#	Time	Username	Problem	Language	Result	Execution time	Memory
237310		jhnah917	Bridges (APIO19_bridges)	C++14	13 / 100	142 ms	10616 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;
    }
};

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 unsigned sz = 1u << 17u;
struct Sub2_Seg{
    int tree[1u << 18u]{};
    Sub2_Seg(){ memset(tree, 0x3f, sizeof tree); }
    void update(unsigned x, int v){
        x |= sz; tree[x] = v;
        while(x >>= 1u) tree[x] = min(tree[x << 1u], tree[x << 1u | 1u]);
    }
    int query(unsigned l, unsigned r){
        l |= sz; r |= sz;
        int ret = tree[0];
        while(l <= r){
            if(l & 1u) ret = min(ret, tree[l++]);
            if(~r & 1u) ret = min(ret, tree[r--]);
            l >>= 1u; r >>= 1u;
        }
        return ret;
    }
};

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{
            int left = a, right = a;
            int l = 1, r = a;
            while(l < r){
                int mid = (l + r) / 2;
                if(mid == a) break;
                if(seg.query(mid, a-1) < b) l = mid + 1;
                else r = mid;
            }
            left = r;
            l = a, b = n-1;
            while(l < r){
                int mid = (l + r + 1) / 2;
                if(seg.query(a, mid) < b) r = mid - 1;
                else l = mid;
            }
            right = l + 1;
            if(seg.query(a, a) < b) right = a;
            cout << right - left + 1 << "\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;
    }
}

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