Submission #983197

#TimeUsernameProblemLanguageResultExecution timeMemory
983197vjudge1Bridges (APIO19_bridges)C++17
29 / 100
640 ms30772 KiB
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int tt = 1, n, m;
ll a[200001], b[200001], c[200001];
vector<pair<int, ll>> g[200005];
ll mn[4 * 200005];
void up(int l, int r, int ind, int num, int v){
    if(l > ind || r < ind) return;
    if(l == r){
        mn[v] = num;
        return;
    }
    int mid = (l + r) / 2;
    up(l, mid, ind, num, v * 2);
    up(mid + 1, r, ind, num, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
int get_mn(int l, int r, int l1, int r1, int v){
    if(l > r1 || l1 > r) return 1e9;
    if(l >= l1 && r1 >= r) return mn[v];
    int mid = (l + r) / 2;
    return min(get_mn(l, mid, l1, r1, v * 2), get_mn(mid + 1, r, l1, r1, v * 2 + 1));
}
bool us[200005];
bool ok = 0;
pair<ll, pair<int, int>> p[200005], p1[200005];
int cnt[200005], pr[200005], sz[200005];
vector<int> v[200005];
void join(int a, int b){
    a = pr[a];
    b = pr[b];
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    for(int to : v[b])
        pr[to] = a;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if(n - 1 != m) ok = 1;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> c[i];
        if(a[i] != i || b[i] != i + 1) ok = 1;
        up(1, m, i, c[i], 1);
        p[i] = {c[i], {a[i], b[i]}};
    }
    for(int i = 1; i <= n; i++){
        pr[i] = i;
        sz[i] = 1;
        v[i].push_back(i);
    }
    cin >> tt;
    if(n <= 1000 && m <= 1000 && tt <= 10000){
        for(int i = 1; i <= tt; i++){
            int type;
            cin >> type;
            if(type == 1){
                ll p, num;
                cin >> p >> num;
                c[p] = num; 
            }
            else{
                ll x, w;
                cin >> x >> w; 
                queue<int> q;
                for(int i = 1; i <= n; i++){
                    g[i].clear();
                    us[i] = 0;
                }
                for(int i = 1; i <= m; i++){
                    g[a[i]].push_back({b[i], c[i]});
                    g[b[i]].push_back({a[i], c[i]});
                }
                q.push(x);
                us[x] = 1;
                int kol = 1;
                while(!q.empty()){
                    int d = q.front();
                    q.pop();
                    for(auto to : g[d]){
                        if(!us[to.first] && to.second >= w){
                            kol++;
                            us[to.first] = 1;
                            q.push(to.first);
                        }
                    }
                }
                cout << kol << "\n";
            }
        }
        return 0;
    }
    if(!ok){
        for(int i = 1; i <= tt; i++){
            int type;
            cin >> type;
            if(type == 1){
                ll p, num;
                cin >> p >> num;
                up(1, m, p, num, 1);
            }
            else{
                ll x, num;
                cin >> x >> num;
                int L = 0, R = x;
                while(L + 1 < R){
                    int mid = (L + R) / 2;
                    if(get_mn(1, m, mid, x - 1, 1) >= num) R = mid;
                    else L = mid;
                }
                int ans = (x - R);
                // cout << ans << "\n";
                L = x - 1, R = n;
                while(L + 1 < R){
                    int mid = (L + R) / 2;
                    if(get_mn(1, m, x, mid, 1) >= num) L = mid;
                    else R = mid;
                }
                ans += (L - x + 1);
                // cout << i << " " << L << "\n";
                cout << ans + 1 << "\n";
            }
        }
        return 0;
    }
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= tt; i++){
        ll type, x, num;
        cin >> type >> x >> num;
        p1[i] = {num, {x, i}};
    }
    sort(p1 + 1, p1 + tt + 1);
    int pos = 1;
    for(int i = 1; i <= tt; i++){
        while(pos <= n && p[pos].first <= p1[i].first){
            join(p[pos].second.first, p[pos].second.second);
            pos++;
        }
        cnt[p1[i].second.second] = sz[pr[p1[i].second.first]];
    }
    for(int i = 1; i <= tt; i++) cout << cnt[i] << "\n";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...