Submission #397972

#	Time	Username	Problem	Language	Result	Execution time	Memory
397972		IloveN	Bridges (APIO19_bridges)	C++14	100 / 100	1748 ms	172888 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e5 + 10;
const int block = 400;

struct query {int tp, x, y;};
int n, m, q, d[N], mark[N], ans[N], p[N], sz[N];
pii E[N];
query Q[N];
vi ad[N];

bool cmp(int x, int y) { return d[x] > d[y];}
bool cmp2(int x, int y) { return Q[x].y > Q[y].y;}

int find_root(int u) { return p[u] > 0 ? (p[u] = find_root(p[u])) : u;}

void merg(int u, int v)
{
    if (u==v) return;
    if (p[u] > p[v]) swap(u, v);
    if (p[u] == p[v]) --p[u];
    p[v] = u;
    sz[u] += sz[v];
}

vi G[N];
int vis[N], res;

void dfs(int u)
{
    vis[u] = 1;
    res += sz[u];
    for (int v : G[u])
        if (!vis[v]) dfs(v);
}

int main()
{
    //freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> E[i].fi >> E[i].se >> d[i];
    cin >> q;
    for (int i = 1; i <= q; ++i) cin >> Q[i].tp >> Q[i].x >> Q[i].y;
    vi sorted_E;
    for (int i = 1; i <= m; ++i) sorted_E.eb(i);
    sort(all(sorted_E), cmp);
    for (int i = 1; i <= q; ++i) ad[i].reserve(block);
    vi normal_edge;
    normal_edge.reserve(m);
    for (int sta = 1; sta <= q; sta += block)
    {
        int en = min(sta + block - 1, q);
        vi spe_edge, Q2;
        for (int i = sta; i <= en; ++i)
            if (Q[i].tp == 1)
            {
                if (!mark[Q[i].x]) mark[Q[i].x] = 1, spe_edge.eb(Q[i].x);
            }
            else Q2.eb(i);
        for (int i = sta; i <= en; ++i)
            if (Q[i].tp == 1) d[Q[i].x] = Q[i].y;
            else
            {
                for (int x : spe_edge)
                    if (d[x] >= Q[i].y) ad[i].eb(x);
            }
        sort(all(Q2), cmp2);
        normal_edge.clear();
        for (int i : sorted_E)
            if (!mark[i]) normal_edge.eb(i);
            else mark[i] = 0;
        for (int i = 1; i <= n; ++i) p[i] = 0, sz[i] = 1;
        int j = 0;
        for (int id : Q2)
        {
            while (j < (int)normal_edge.size() && d[normal_edge[j]] >= Q[id].y)
            {
                pii pa = E[normal_edge[j]];
                merg(find_root(pa.fi), find_root(pa.se));
                ++j;
            }
            stack<int> st;
            for (int i : ad[id])
            {
                int u = find_root(E[i].fi);
                int v = find_root(E[i].se);
                if (u != v)
                {
                    G[u].eb(v);
                    G[v].eb(u);
                    st.push(u);
                    st.push(v);
                }
            }
            res = 0;
            dfs(find_root(Q[id].x));
            vis[find_root(Q[id].x)] = 0;
            ans[id] = res;
            while (!st.empty()) G[st.top()].clear(), vis[st.top()] = 0, st.pop();
        }
        sort(all(spe_edge), cmp);
        merge(all(normal_edge), all(spe_edge), sorted_E.begin(), cmp);
    }
    for (int i = 1; i <= q; ++i)
        if (Q[i].tp == 2) cout << ans[i] << "\n";
    return 0;
}

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