Submission #918493

#	Time	Username	Problem	Language	Result	Execution time	Memory
918493		cpptowin	Bridges (APIO19_bridges)	C++17	0 / 100	3041 ms	21124 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(50010);
array<int,3> edge[maxn];
array<int,3> qry[maxn];
int n,m,q;
int ans[maxn];
bool ok[maxn];
void solve(int l,int r)
{
    fo(i,1,n) g.make(i);
    vi changed;
    vector<array<int,3>> v;
    fo(i,1,m) ok[i] = 0;
    fo(i,l,r)
    {
        if(qry[i][0] > 0) ok[i] = 1,changed.pb(i);
        else v.pb(qry[i]);
    }
    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]);
    });
//    for(auto [index,x,y] : v) cout << index << ' ' << x << ' ' << y << "\n";
//    for(int it : changed) cout << it << "\n";
    fo(i,l,r)
    {
        if(qry[i][0] < 0)
        {
            int timer = g.st.size();
            for(auto [index,x,y] : v)
            {
                if(index == -i) break;
                if(index > 0)
                {
                    g.Union(index,x);
//                    cout << index << ' '<< x << "uv\n";
                }
            }
            for(int it : changed) if(edge[it][2] >= qry[i][2])
                g.Union(edge[it][0],edge[it][1]);
//                cout << edge[it][0] << ' ' << edge[it][1] << "cc\n";
            ans[i] = g.sz[g.find(qry[i][1])];
            g.rollback(timer);
//            cout << "xxxxxxxxxx \n";
        }
        else edge[qry[i][1]][2] = qry[i][2];
    }

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

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