Submission #237313

#	Time	Username	Problem	Language	Result	Execution time	Memory
237313		jhnah917	Bridges (APIO19_bridges)	C++14	13 / 100	133 ms	8312 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 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 mid = (s + e) >> 1;
        if(x <= mid) update(x, v, node << 1, s, mid);
        else update(x, v, node << 1 | 1, mid + 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;
            else return s;
        }
        if(e <= x && tree[node] >= v) return 0;
        int mid = (s + e) >> 1;
        if(queryL(x, v, node << 1 | 1, mid+1, e)) return x;
        return queryL(x, v, node << 1, s, mid);
    }
    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;
            else return s;
        }
        if(x <= s && tree[node] >= v) return n;
        int mid = (s + e) >> 1;
        if(queryR(x, v, node << 1, s, mid) != n) return x;
        return queryR(x, v, node << 1 | 1, mid+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";
        }
    }
}

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