Submission #707613

#	Time	Username	Problem	Language	Result	Execution time	Memory
707613		He_Huanglu	Bridges (APIO19_bridges)	C++17	59 / 100	3031 ms	4832 KiB

bridges

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

const int N = 5e4 + 5, L = 1e5 + 5;
int n, m, q, from[L], to[L], d[L], par[N], ok[L], ans[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 = sqrt(q);
    int lim = ceil(1.0 * q / S);
    for(int t = 0; t < lim; t++)
    {
        vector <pair<int, ii> > change, query;
        vector <int> remain;
        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});
            }
            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;
//            if(t == 2) cout << id << " " << x << " " << w << "***\n";
//            if(t == 2)
//            {
//                for(auto i : remain)
//                {
//                    cout << i << " " << d[i] << "\n";
//                }
//            }
            while (it < remain.size() && d[remain[it]] >= w)
            {
                int i = remain[it];
//                if(t == 2) cout << i << " : " << from[i] << " " << to[i] << " " << d[i] << "^^\n";
                join(from[i], to[i], 0);
                it++;
            }
            for(auto[jd, _e] : change)
            {
                int i = _e.fi, r = _e.se;
//                if(t == 2) cout << i << " " << jd << " " << ok[i] << " " << r << "$$$\n";
                if(jd < id && r >= w && ok[i] != 2)
                {
                    join(from[i], to[i], 1);
//                    if(t == 2) cout << i << " : " << from[i] << " " << to[i] << " " << r << "^^^^\n";
                }
                if(jd < id)
                {
                    ok[i] = 2;
                    _st.push(i);
//                    if(t == 2) cout << i << " " << jd << " " << id << "*****\n";
                }
            }
            ans[id] = -par[root(x)];
//            if(t == 2) cout << id << " " << ans[id] << "\n";
            undo();
        }
        for(int i = t * S + 1; i <= min(q, (t + 1) * S); i++)
        {
            if(lst[i].fi == 1)
            {
                ok[lst[i].se.fi] = 0;
                d[lst[i].se.fi] = lst[i].se.se;
//                cout << lst[i].se.fi << " " << d[lst[i].se.fi] << "##\n";
            }
        }
    }
    for(int i = 1; i <= q; i++) if(lst[i].fi == 2) cout << ans[i] << "\n";

}

Compilation message (stderr)

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

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