Submission #798577

#	Time	Username	Problem	Language	Result	Execution time	Memory
798577		gg123_pe	Bridges (APIO19_bridges)	C++14	43 / 100	426 ms	16984 KiB

bridges

#include <bits/stdc++.h> 
using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 50005, M = 1e5 + 5, inf = 2e9; 

int n, m; 
int ans; 
int U[M], V[M], W[M];
bool vis[N];  
vector <pair<int,int>> adj[N]; 
vector <pair<int, pair<int,int>>> edges; 

void clear(){
    ans = 0; 
    f(i,1,n+1) vis[i] = 0, adj[i].clear(); 
}
void add(){
    f(i,1,m+1){
        adj[U[i]].push_back({V[i], W[i]}); 
        adj[V[i]].push_back({U[i], W[i]}); 
    }
}
void dfs(int u, int wa){
    ans++; 
    vis[u] = 1; 
    for(auto p: adj[u]){
        int v = p.first, w = p.second; 
        if(vis[v] or w < wa) continue; 
        dfs(v, wa); 
    }
}
void subtask_1(){
    int q; cin >> q; 

    while(q--){
        int ty, x, w; 
        cin >> ty >> x >> w; 
         
        if(ty == 1){
            W[x] = w; 
        }
        if(ty == 2){
            add(); 
            dfs(x, w); 
            cout << ans << "\n"; 
            clear(); 
        }
    }
}
struct st{
    int n, st[4*N]; 
    void build(int id, int l, int r){
        if(l == r){
            st[id] = inf; 
            return; 
        }
        int m = (l+r)>>1; 
        build(id<<1, l, m), build(id<<1|1, m+1, r); 
        st[id] = inf; 
    }
    void upd(int id, int l, int r, int pos, int val){
        if(r < pos or pos < l) return; 
        if(l == r){
            st[id] = val; 
            return; 
        }
        int m = (l+r)>>1; 
        if(pos <= m) upd(id<<1, l, m, pos, val); 
        else upd(id<<1|1, m+1, r, pos, val); 
        st[id] = min(st[id<<1], st[id<<1|1]); 
    }
    int query(int id, int l, int r, int x, int y){
        if(r < x or y < l) return inf; 
        if(x <= l and r <= y) return st[id]; 
        int m = (l+r)>>1; 
        return min(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y)); 
    }
    void Upd(int pos, int val){
        upd(1, 1, n, pos, val); 
    }
    int Que(int x, int y){
        return query(1, 1, n, x, y); 
    }
}st; 

void subtask_2(){
    st.n = n; 
    f(i,1,n){
        st.Upd(i, W[i]); 
    }
    int q; cin >> q; 
    while(q--){
        int ty, x, w; 
        cin >> ty >> x >> w; 

        if(ty == 1){
            st.Upd(x, w); 
            W[x] = w; 
        }
        else{
            int res = 1;    
            int l, r; 
            if(W[x-1] >= w){
                l = 1, r = x-1; 
                while(l < r){
                    int m = (l+r)>>1; 
                    if(st.Que(m, x-1) >= w) r = m; 
                    else l = m+1; 
                }
                res += (x - l); 
            }
            if(W[x] >= w){
                l = x, r = n-1; 
                while(l < r){
                    int m = (l+r+1)>>1; 
                    if(st.Que(x, m) >= w) l = m; 
                    else r = m-1; 
                }
                res += (l - x + 1); 
            }
            cout << res << "\n"; 
        }
    }
}
int ct; 
int p[2*M], sz[2*M], we[2*M]; 
int child[2*M][2], up[2*M][17]; 
bool on[2*M]; 

void ini(){
    ct = n+1; 
    f(i,1,n+1) sz[i] = 1, p[i] = i, we[i] = inf; 
}
int find(int x){
    if(p[x] == x) return x; 
    return p[x] = find(p[x]); 
}
void uni(int u, int v, int w){
    u = find(u), v = find(v); 
    if(u == v) return; 
    p[u] = p[v] = p[ct] = ct; 
    child[ct][0] = u, child[ct][1] = v; 
    on[u] = on[v] = true; 
    we[ct] = w; 
    ct++; 
}
void go(int u, int f){
    up[u][0] = f; 
    f(i,1,17) up[u][i] = up[up[u][i-1]][i-1]; 
    
    f(i,0,2){
        if(child[u][i] == 0) continue; 
        go(child[u][i], u); 
        sz[u] += sz[child[u][i]]; 
    }
}
void subtask_4(){
    if((int) edges.size() > 0)
        sort(edges.begin(), edges.end()); 
    ini(); 
    for(auto p: edges){
        int w = abs(p.first), u = p.second.first, v = p.second.second; 
        uni(u, v, w); 
    }

    f(i,1,ct) if(!on[i]) go(i, 0); 

    int q; cin >> q; 
    while(q--){
        int ty, x, w; 
        cin >> ty >> x >> w; 

        // siempre es 2
        fa(i,16,0){
            if(up[x][i] == 0 or we[up[x][i]] < w) continue; 
            x = up[x][i]; 
        }
        cout << sz[x] << "\n"; 
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    cin >> n >> m; 

    bool chain = true; 

    f(i,1,m+1){
        cin >> U[i] >> V[i] >> W[i]; 
        edges.push_back({-W[i], {U[i], V[i]}}); 

        if(V[i] != U[i] + 1) chain = false; 
    }

    if(n <= 1000 and m <= 1000){
        subtask_1(); 
        return 0; 
    }
    if(chain){
        subtask_2(); 
        return 0; 
    }
    subtask_4(); 

    return 0; 
}

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