Submission #983175

#	Time	Username	Problem	Language	Result	Execution time	Memory
983175		vjudge1	Bridges (APIO19_bridges)	C++17	29 / 100	361 ms	13000 KiB

bridges

#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;
const ll N = 400400;
ll s[N], T = 1;

ll get(ll l, ll r, ll res = 1e18)
{
    l += T - 1, r += T - 1;
    for(; l <= r; l >>= 1, r >>= 1)
    {
        if(l % 2 == 1) res = min(res, s[l++]);
        if(r % 2 == 0) res = min(res, s[r--]);
    }
    return res;
}
void upd(ll i, ll x)
{
    i += T - 1;
    s[i] = x;
    for(; i > 1; i >>= 1)
        s[i >> 1] = min(s[i], s[i ^ 1]);

}

void solve()
{
    ll n, m, Q, i, j, k;
    cin >> n >> m;
    while(T < m) T *= 2;
    vector<pair<ll, ll>> v[n + 1];
    ll x[m + 1], y[m + 1], z[m + 1];
    for(i = 1; i <= m; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        x[i] = a, y[i] = b, z[i] = c;
    }

    cin >> Q;

    if(n <= 1000 && m <= 1000 && Q <= 10000)
    {
        while(Q--)
        {
            ll t, u, k;
            cin >> t >> u >> k;
            if(t == 1)
            {
                for(auto &i : v[x[u]])
                    if(i.first == y[u] && i.second == z[u])
                    {
                        i.second = k;
                        break;
                    }
                for(auto &i : v[y[u]])
                    if(i.first == x[u] && i.second == z[u])
                    {
                        i.second = k;
                        break;
                    }
                z[u] = k;
                continue;
            }
            ll us[n + 1] = {};
            queue<ll> q;
            q.push(u);
            us[u] = 1;
            ll ans = 1;
            while(q.sz)
            {
                ll s = q.front();
                q.pop();
                for(auto [t, c] : v[s])
                {
                    if(us[t] || c < k) continue;
                    q.push(t);
                    us[t] = 1;
                    ++ans;
                }
            }
            cout << ans << '\n';
        }
        return;
    }

    for(i = 1; i <= m; ++i)
        upd(i, z[i]);
    while(Q--)
    {
        ll t, u, k;
        cin >> t >> u >> k;
        if(t == 1)
        {
            upd(u, k);
            continue;
        }
        ll ans = 1;
        ll l = u + 1, r = n;
        while(l <= r)
        {
            ll mid = (l + r) / 2;
            ll c = get(u, mid - 1);
            if(c >= k && (mid == n || get(u, mid) < k))
            {
                ans += mid - u;
                break;
            }
            if(c >= k)
                l = mid + 1;
            else
                r = mid - 1;
        }
        l = 1, r = u - 1;
        while(l <= r)
        {
            ll mid = (l + r) / 2;
            ll c = get(mid, u - 1);
            if(c >= k && (mid == 1 || get(mid - 1, u - 1) < k))
            {
                ans += u - mid;
                break;
            }
            if(c >= k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        cout << ans << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:29:20: warning: unused variable 'j' [-Wunused-variable]
   29 |     ll n, m, Q, i, j, k;
      |                    ^
bridges.cpp:29:23: warning: unused variable 'k' [-Wunused-variable]
   29 |     ll n, m, Q, i, j, k;
      |                       ^

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