Submission #1116415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116415		LonlyR	Bridges (APIO19_bridges)	C++17	14 / 100	678 ms	10948 KiB

bridges

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 100005, bl = 450;
int n, m, q;
int par[maxn], change[maxn], mark[maxn], ans[maxn];
array<int, 3> e[maxn];
vector<tuple<int,int,int>> upd;
vector<array<int, 3>> qr;
vector<tuple<int,int,int,int>> edge, version;

int root(int x)
{
    while (par[x] > 0)
        x = par[x];
    return x;
}

void unite(int u, int v)
{
    if ((u = root(u)) == (v = root(v))) return;
    if (par[u] > par[v]) swap(u, v);
    version.emplace_back(u, par[u], v, par[v]);
    par[u] += par[v];
    par[v] = u;
}

void rollback(int last)
{
    while (version.size() > last)
    {
        auto [u, v, x, y] = version.back();
        version.pop_back();
        par[u] = v;
        par[x] = y;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w,
        edge.emplace_back(w, u, v, i),
        e[i] = {u, v, w};
    sort(all(edge), greater<>());
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int t, x, y; cin >> t >> x >> y;
        if (t == 1) upd.emplace_back(i, x, y);
        else qr.push_back({y, x, i});
        if (i % bl == 0 || i == q)
        {
            if (qr.empty()) continue;
            sort(all(qr));
            for (int j = 1; j <= n; j++)
                par[j] = -1;
            version.clear();
            for (auto [time, id, w] : upd)
                change[id] = 1;
            int pt = (int)qr.size() - 1;
            for (auto [w, u, v, id] : edge)
            {
                if (change[id]) continue;
                while (pt >= 0 && qr[pt][0] > w)
                {
                    int last = version.size();
                    /// find order
                    int j = 0;
                    for (; j < upd.size(); j++)
                    {
                        auto [time, id, w] = upd[j];
                        if (qr[pt][2] < time) break;
                    }
                    for (int k = j - 1; k >= 0; k--)
                    {
                        auto [time, id, w] = upd[k];
                        assert(time < qr[pt][2]);
                        if (!mark[id] && w >= qr[pt][0])
                            unite(e[id][0], e[id][1]);
                        mark[id] = w;
                    }
                    for (int k = j; k < upd.size(); k++)
                    {
                        auto [time, id, w] = upd[k];
                        assert(time > qr[pt][2]);
                        w = (mark[id] ? mark[id] : e[id][2]);
                        if (w >= qr[pt][0])
                            unite(e[id][0], e[id][1]);
                    }
                    ans[qr[pt][2]] = -par[root(qr[pt][1])];
                    rollback(last);
                    for (int k = j - 1; k >= 0; k--)
                    {
                        auto [time, id, w] = upd[k];
                        mark[id] = 0;
                    }
                    pt--;
                }
                unite(u, v);
            }
            /// left
            while (pt >= 0)
            {
                int last = version.size();
                /// find order
                int j = 0;
                for (; j < upd.size(); j++)
                {
                    auto [time, id, w] = upd[j];
                    if (qr[pt][2] < time) break;
                }
                for (int k = j - 1; k >= 0; k--)
                {
                    auto [time, id, w] = upd[k];
                    assert(time < qr[pt][2]);
                    if (!mark[id] && w >= qr[pt][0])
                        unite(e[id][0], e[id][1]);
                    mark[id] = w;
                }
                for (int k = j; k < upd.size(); k++)
                {
                    auto [time, id, w] = upd[k];
                    assert(time > qr[pt][2]);
                    w = (mark[id] ? mark[id] : e[id][2]);
                    if (w >= qr[pt][0])
                        unite(e[id][0], e[id][1]);
                }
                ans[qr[pt][2]] = -par[root(qr[pt][1])];
                rollback(last);
                for (int k = j - 1; k >= 0; k--)
                {
                    auto [time, id, w] = upd[k];
                    mark[id] = 0;
                }
                pt--;
            }
            for (auto [time, id, w] : upd)
                change[id] = 0,
                e[id][2] = w;
            upd.clear();
            qr.clear();
        }
    }
    for (int i = 1; i <= q; i++)
        if (ans[i])
            cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:31:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     while (version.size() > last)
      |            ~~~~~~~~~~~~~~~^~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                     for (; j < upd.size(); j++)
      |                            ~~^~~~~~~~~~~~
bridges.cpp:89:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                     for (int k = j; k < upd.size(); k++)
      |                                     ~~^~~~~~~~~~~~
bridges.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for (; j < upd.size(); j++)
      |                        ~~^~~~~~~~~~~~
bridges.cpp:127:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                 for (int k = j; k < upd.size(); k++)
      |                                 ~~^~~~~~~~~~~~

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