Submission #707623

#	Time	Username	Problem	Language	Result	Execution time	Memory
707623		He_Huanglu	Bridges (APIO19_bridges)	C++17	100 / 100	2441 ms	5836 KiB

bridges

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 5e4 + 2, L = 1e5 + 2;
int n, m, q, from[L], to[L], d[L], par[N], ans[L];
short ok[L];
pair<int, ii> lst[L];
stack <ii> st;
stack <int> _st;


int root(int u)
{
    return par[u] < 0 ? u : root(par[u]);
}
void join(int u, int v, int tp)
{
    u = root(u), v = root(v);
    if(u == v) return ;
    if(par[u] > par[v]) swap(u, v);
    if(tp)
    {
        st.push({v, par[v]});
        st.push({u, par[u]});
    }
    par[u] += par[v];
    par[v] = u;
}
void undo()
{
    while (!st.empty())
    {
        par[st.top().fi] = st.top().se;
        st.pop();
    }
    while (!_st.empty())
    {
        ok[_st.top()] = 1;
        _st.pop();
    }
}


main ()
{
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r"))
    {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> from[i] >> to[i] >> d[i];
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> lst[i].fi >> lst[i].se.fi >> lst[i].se.se;
    }
    const int S = 1000;
    int lim = ceil(1.0 * q / S);
    for(int t = 0; t < lim; t++)
    {
        vector <pair<int, ii> > change, query;
        vector <int> remain;
        vector <ii> vt;
        for(int i = min(q, (t + 1) * S); i >= t * S + 1; i--)
        {
            if(lst[i].fi == 1)
            {
                ok[lst[i].se.fi] = 1;
                change.push_back({i, lst[i].se});
                vt.push_back(lst[i].se);
            }
            else query.push_back({i, lst[i].se});
        }
        for(int i = 1; i <= m; i++)
        {
            if(!ok[i]) remain.push_back(i);
            else change.push_back({0, {i, d[i]}});
        }
        sort(remain.begin(), remain.end(), [] (int x, int y) {
             return d[x] > d[y];
        });
        sort(query.begin(), query.end(), [] (pair<int, ii> x, pair<int, ii> y) {
             return x.se.se > y.se.se;
        });
        for(int i = 1; i <= n; i++) par[i] = -1;
        while (!st.empty()) st.pop();
        int it = 0;
        for(auto[id, e] : query)
        {
            int x = e.fi, w = e.se;
            while (it < remain.size() && d[remain[it]] >= w)
            {
                int i = remain[it];
                join(from[i], to[i], 0);
                it++;
            }
            for(auto[jd, _e] : change)
            {
                int i = _e.fi, r = _e.se;
                if(jd < id)
                {
                    if(r >= w && ok[i] != 2) join(from[i], to[i], 1);
                    ok[i] = 2;
                    _st.push(i);
                }
            }
            ans[id] = -par[root(x)];
            undo();
        }
        for(int i = vt.size() - 1; i >= 0; i--)
        {
            ii e = vt[i];
            ok[e.fi] = 0;
            d[e.fi] = e.se;
        }
    }
    for(int i = 1; i <= q; i++) if(lst[i].fi == 2) cout << ans[i] << "\n";

}

Compilation message (stderr)

bridges.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main ()
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             while (it < remain.size() && d[remain[it]] >= w)
      |                    ~~~^~~~~~~~~~~~~~~
bridges.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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