Submission #934047

#	Time	Username	Problem	Language	Result	Execution time	Memory
934047		leo_2727	Bridges (APIO19_bridges)	C++17	0 / 100	145 ms	46016 KiB

bridges

//16 points
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#include <cmath>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <unordered_map>
#define F first
#define S second
#define PB push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<pair<int, ii>> viii;
typedef vector<vii> vvii;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int n, m;
vector<pair<ii, int>> bridges;
vi mp, ar;
vvii al;
bool vis[50005];

class SegmentTree{
private:
    vi st;
    int len;
public:
    void getSize(int x){    len=x;  st.resize(4*x); }
    int calculate(int node){   return min(st[node*2], st[node*2+1]);   }
    void build(vi& ar, int node, int l, int r){
        if(l==r)    st[node]=ar[l];
        else{
            int m=(l+r)/2;
            build(ar, node*2, l, m);
            build(ar, node*2+1, m+1, r);
            st[node]=calculate(node);
        }
    }
    //node initially 1, l is left of array, r is right of array, x is pos, y is new value
    void update(int node, int l, int r, int x, int y){
        if(l==r)    st[node]=y;
        else{
            int m=(l+r)/2;
            if(x<=m)    update(node*2, l, m, x, y);
            else        update(node*2+1, m+1, r, x, y);
            st[node]=calculate(node);
        }
    }
    //segment querys, l is left in array, r is rigth on array
    //x and y are boundarys of segment of query
    int query(int node, int l, int r, int x, int y){
        if(x<=l && r<=y)    return st[node];
        else{
            int ans=1e9;
            int m=(l+r)/2;
            if(x<=m)    ans=min(ans, query(node*2, l, m, x, y));
            if(y>=m+1)  ans=min(ans, query(node*2+1, m+1, r, x, y));
            return ans;
        }
    }
};

void getCost(int node, int p, int cost){
    ar[mp[node]]=cost;
    for(auto ch:al[node])
        if(ch.F!=p) getCost(ch.F, node, ch.S);
}


void remap(int node, int p, int curr){
    mp[curr]=node;
    for(auto ch:al[node])
        if(ch.F!=p)   remap(ch.F, node, curr+1);
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    al.resize(n+1, vii ());
    bridges.resize(m+1);
    mp.resize(n+1, 0);
    ar.resize(n+1, 0);
    for(int i=1;i<=m;i++){
        int x, y, w;
        cin>>x>>y>>w;
        al[x].PB({y, w});
        al[y].PB({x, w});
        bridges[i]={{x, y}, w};
    }
    for(int i=1;i<=n;i++)
        if(al[i].size()==1){
            remap(i, 0, 1);
            break;
        }
    getCost(mp[1], 0, 0);
    SegmentTree preff;
    preff.getSize(n);   preff.build(ar, 1, 1, n);
    ar.assign(n+1, 0);
    getCost(mp[n], 0, 0);
    SegmentTree suff;
    suff.getSize(n);    suff.build(ar, 1, 1, n);
    int q;  cin>>q;
    while(q--){
        int type, x, y;
        cin>>type>>x>>y;
        if(type==1){
            int a=bridges[x].F.F, b=bridges[x].F.S, w=bridges[x].S;
            bridges[x]={{a, b}, y};
            if(mp[a]>mp[b]) swap(a, b);
            preff.update(1, 1, n, mp[b], y);
            suff.update(1, 1, n, mp[a], y);
        }
        else{
            int ans=0;
            int pos=n;
            for(int k=(n-mp[x])/2;k>=1;k/=2)
                while(pos-k>=mp[x] && preff.query(1, 1, n, mp[x], pos)>y)   pos-=k;
            ans+=pos-mp[x];
            pos=1;
            for(int k=mp[x]/2;k>=1;k/=2)
                while(pos+k<=mp[x] && suff.query(1, 1, n, pos, mp[x])>y)    pos+=k;
            ans+=mp[x]-pos;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main(int, const char**)':
bridges.cpp:120:53: warning: unused variable 'w' [-Wunused-variable]
  120 |             int a=bridges[x].F.F, b=bridges[x].F.S, w=bridges[x].S;
      |                                                     ^

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