Submission #918840

#	Time	Username	Problem	Language	Result	Execution time	Memory
918840		cpptowin	Bridges (APIO19_bridges)	C++17	100 / 100	1665 ms	421164 KiB

bridges

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
//#define int long long
//#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 1024;
const int mod = 1e9 + 7;
struct event
{
    int u,szu,v,szv;
    event(int u,int szu,int v,int szv) : u(u),szu(szu),v(v),szv(szv) {};
};
struct DSU
{
    vi par,sz;
    DSU(int n) : par(n),sz(n) {};
    stack<event> st;
    void rollback(int x)
    {
        if(st.empty()) return;
        while(st.size() > x)
        {
            auto top = st.top();
            st.pop();
            par[top.v] = top.v;
            sz[top.v] = top.szv;
            par[top.u] = top.u;
            sz[top.u] = top.szu;
        }
    }
    void make(int u)
    {
        par[u] = u;
        sz[u] = 1;
    }
    int find(int u)
    {
        return u == par[u] ? u : find(par[u]);
    }
    void Union(int u,int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return ;
        if(sz[u] < sz[v]) swap(u,v);
        st.push(event(u, sz[u], v, sz[v]));
        sz[u] += sz[v];
        par[v] = u;
    }
}g(100010);
array<int,3> edge[maxn];
array<int,3> qry[maxn];
int n,m,q;
int ans[maxn];
bool ok[maxn];
vii join[maxn];
void solve(int l,int r)
{
    fo(i,1,n) g.make(i);
    vi changed,query;
    vector<array<int,3>> v;
    fo(i,1,m) ok[i] = 0;
    fo(i,l,r)
    {
        if(qry[i][0] > 0) ok[qry[i][1]] = 1,changed.pb(qry[i][1]);
        else query.pb(i);
    }
//    for(int it : changed) cout << it << ' ' ;en;
    fo(i,1,m) if(!ok[i]) v.pb(edge[i]);
    sort(v.begin(),v.end(),[](array<int,3> a,array<int,3> b)
    {
        return a[2] > b[2] or (a[2] == b[2] and a[0] > b[0]);
    });
    sort(query.begin(),query.end(),[](int a,int b)
         {
             return qry[a][2] > qry[b][2];
         });
    fo(i,l,r)
    {
        if(qry[i][0] < 0)
        {
            for(int it : changed) if(edge[it][2] >= qry[i][2]) join[i].pb(edge[it][0],edge[it][1]);
        }
        else edge[qry[i][1]][2] = qry[i][2];
    }
    int ptr = 0;
    for(int it : query)
    {
        while(ptr < (int)v.size() and v[ptr][2] >= qry[it][2]) g.Union(v[ptr][0],v[ptr][1]),ptr++;
        int timer = g.st.size();
        for(auto [u,v] : join[it]) g.Union(u,v);
        ans[it] = g.sz[g.find(qry[it][1])];
        g.rollback(timer);
    }
}
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    fo(i,1,m) cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
    cin >> q;
    fo(i,1,q)
    {
        cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
        if(qry[i][0] == 1) qry[i][0] = i;
        else qry[i][0] = -i;
    }
    for(int i = 1 ; i <= q ; i += nsqrt) solve(i,(min(q,i + nsqrt - 1)));
    fo(i,1,q) if(qry[i][0] < 0) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::stack<event>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         while(st.size() > x)
      |               ~~~~~~~~~~^~~
bridges.cpp: At global scope:
bridges.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main()
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(name".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