Submission #1243439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243439		sitingfake	Bridges (APIO19_bridges)	C++20	59 / 100	3092 ms	110512 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
int dx[] = {0 , -1 , 0 , 1};
int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code

const int maxn = 1e5 + 7;

int n , m;

int q;

int NumBlocks , Lim;

int ans[maxn];

iii edges[maxn];

bool changed[maxn];

vector <ii> E[maxn];

struct query
{
    int type;
    int u;
    int w;
    int i;
};

struct Event
{
    int t;
    // 0 -> dsu , 1 -> query
    int w;
    int u;
    int v;
    int id;

    bool operator < (Event & other)
    {
        if(w == other.w) return t < other.t;
        return w > other.w;
    }
};

vector <query> Q[505];

struct Dsu
{
    vector <int> par , sz;

    struct Info
    {
        int u;
        int PrePar;
        int PreSize;
        bool type;
        // 0 -> adjust parent , 1 -> adjust size
    };

    stack <Info> st;

    int num;

    Dsu(int n)
    {
        num = n;
        par = vector <int>(n + 2);
        sz = vector <int> (n + 2 , 1);

        for(int i = 1; i <= num; i++)
        {
            par[i] = i;
        }
    }

    int get(int u)
    {
        while(par[u] != u) u = par[u];
        return u;
    }

    int getsize(int u)
    {
        u = get(u);
        return sz[u];
    }

    bool uni(int u ,int v , bool save)
    {
        u = get(u);
        v = get(v);
        if(u == v) return 0;

        if(sz[u] < sz[v]) swap(u , v);

        if(save)
        {
            st.push({v , par[v] , 0 , 0});
            st.push({u , 0 , sz[u] , 1});
        }

        sz[u] += sz[v];
        par[v] = u;

        return 1;
    }

    void RollBack(int target)
    {
        while(st.size() > target)
        {
            Info tmp = st.top();
            st.pop();

            if(tmp.type)
            {
                sz[tmp.u] = tmp.PreSize;
            }
            else
            {
                par[tmp.u] = tmp.PrePar;
            }
        }
    }

    void Reset()
    {
        while(!st.empty()) st.pop();
        for(int i = 1; i <= num; i++)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }
};

void solve(void)
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        cin >> edges[i].se.fi >> edges[i].se.se >> edges[i].fi;
    }

    cin >> q;

    Lim = sqrt(q + 1);
    NumBlocks = (q + Lim - 1) / Lim;
    for(int i = 1; i <= q; i++)
    {
        int id = (i + Lim - 1) / Lim;
        query tmp;

        cin >> tmp.type >> tmp.u >> tmp.w;
        tmp.i = i;

        Q[id].push_back(tmp);
    }

    Dsu dsu(n);

    ms(ans , -1);

    for(int i = 1; i <= NumBlocks; i++)
    {
        vector <Event> tmp;

        for(int j = 0; j < Q[i].size(); j++)
        {
            query it = Q[i][j];

            if(it.type == 1)
            {
                changed[it.u] = 1;
                edges[it.u].fi = it.w;
            }
            else
            {
                tmp.push_back({1 , it.w , it.u , 0 , it.i});

                for(int k = 0; k < Q[i].size(); k++)
                {
                    if(k == j || Q[i][k].type == 2) continue;

                    int val = edges[Q[i][k].u].fi;

                    if(val >= it.w) E[it.i].push_back(edges[Q[i][k].u].se);
                }
            }
        }

        for(int j = 1; j <= m; j++)
        {
            if(!changed[j])
            {
                tmp.push_back({0 , edges[j].fi , edges[j].se.fi , edges[j].se.se , 0});
            }
        }

        sort(all(tmp));

        for(Event it : tmp)
        {
            if(it.t == 0)
            {
                dsu.uni(it.u , it.v , 0);
            }
            else
            {

                for(ii e : E[it.id])
                {
                    dsu.uni(e.fi , e.se , 1);
                }
                ans[it.id] = dsu.getsize(it.u);

                dsu.RollBack(0);
            }
        }

        for(query it : Q[i])
        {
            if(it.type == 1)
            {
                changed[it.u] = 0;
            }
        }

        dsu.Reset();
    }

    for(int i = 1; i <= q; i++)
    {
        if(ans[i] != -1) cout << ans[i] << "\n";
    }
}


/**
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
3
2 1 6
1 1 1
2 1 2
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc; tc = 1;

   while(tc--) solve();

   //execute;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:325:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  325 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:326:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  326 |        freopen(task".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