Submission #934105

#	Time	Username	Problem	Language	Result	Execution time	Memory
934105		vjudge1	Bridges (APIO19_bridges)	C++98	29 / 100	440 ms	3164 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int arr[50001];

struct ST{
    int tree[200001];

    void build(int node, int l, int r){
        if(l==r){
            tree[node]=arr[l];
            return;
        }
        build(2*node+1, l, (l+r)/2);
        build(2*node+2, (l+r)/2+1, r);
        tree[node]=min(tree[2*node+1], tree[2*node+2]);
    }

    void update(int node, int l, int r, int pos, int x){
        if(r<pos || l>pos)
            return;
        if(l==r){
            tree[node]=x;
            return;
        }
        update(2*node+1, l, (l+r)/2, pos, x);
        update(2*node+2, (l+r)/2+1, r, pos, x);
        tree[node]=min(tree[2*node+1], tree[2*node+2]);
    }

    int query(int node, int l, int r, int a, int b){
        if(l>b || r<a)
            return (1<<30);
        if(l>=a && r<=b){
            return tree[node];
        }
        return min(query(2*node+1, l, (l+r)/2, a, b), query(2*node+2, (l+r)/2+1, r, a, b));
    }
};

struct tpos{
    int x, w, pos;
};


int n, m, q, cnt;
ST tree;
vector<vector<tpos>> adj;
int from[1000], to[1000], peso[1000];
bool used[1000];

void busca(int node, int &w){
    used[node]=1;
    cnt++;
    for(tpos it: adj[node]){
        if(used[it.x]==0 && w<=it.w)
            busca(it.x, w);
    }
}

int buscaizq(int l, int r, int pos, int x){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(pos-mid>=0 && tree.query(0, 0, n-1, pos-mid, pos-1)>=x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

int buscadere(int l, int r, int pos, int x){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(pos+mid<n && tree.query(0, 0, n-1, pos+1, pos+mid)>=x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

void solve(){
    cin>> n>> m;
    if(m==n-1){
        int t, a, b, c, x, y;
        for(int i=0; i<m; i++){
            cin>> a>> b>> c;
            arr[i]=c;
        }
        tree.build(0, 0, n-1);
        cin>> q;
        for(int i=0; i<q; i++){
            cin>> t>> a>> b;
            a--;
            if(t==1){
                tree.update(0, 0, n-1, a, b);
            }
            else{
                x=buscaizq(0, n-1, a, b);
                y=buscadere(0, n-1, a-1, b);
                cout<< x+y+1<< "\n";
            }
        }
    }
    else{
        adj.resize(n+1);
        for(int i=0; i<m; i++){
            cin>> from[i]>> to[i]>> peso[i];
            from[i]--;
            to[i]--;
            adj[from[i]].push_back({to[i], peso[i], i});
            adj[to[i]].push_back({from[i], peso[i], i});
        }
        
        cin>> q;
        int t, a, b;
        for(int i=0; i<q; i++){
            cin>> t>> a>> b;
            if(t==1){
                a--;
                for(int j=0; j<adj[from[a]].size(); j++){
                    if(adj[from[a]][j].pos==a){
                        adj[from[a]][j].w=b;
                        break;
                    }
                }
                for(int j=0; j<adj[to[a]].size(); j++){
                    if(adj[to[a]][j].pos==a){
                        adj[to[a]][j].w=b;
                        break;
                    }
                }
            }
            else{
                cnt=0;
                a--;
                busca(a, b);
                cout<< cnt<< "\n";
                memset(used, 0, sizeof(used));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin.tie(0);
    int t=1;
    //cin>> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:126:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tpos>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |                 for(int j=0; j<adj[from[a]].size(); j++){
      |                              ~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:132:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tpos>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |                 for(int j=0; j<adj[to[a]].size(); j++){
      |                              ~^~~~~~~~~~~~~~~~~~

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