Submission #130039

#	Time	Username	Problem	Language	Result	Execution time	Memory
130039		combi1k1	Bridges (APIO19_bridges)	C++14	13 / 100	3108 ms	524288 KiB

bridges

#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;

const int   N   = 5e4 + 5;
const int   B   = 317;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()
#define X       first
#define Y       second

typedef pair<int,int>   ii;
typedef pair<int,ii>    pii;

struct Edge {
	int x, y;
	int w, i;
	bool operator < (const Edge &a) const   {
        return  w > a.w;
	}
};
struct Ques {
    int mas, ver, idx;
    bool operator < (const Ques& a) const   {
        return  mas > a.mas;
    }
};

bool uV[N];
bool uE[100005];

namespace DSU   {
    int p[N], s[N];
    int lead(int x) {
        return  p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (uV[y] > uV[x] || (uV[y] == uV[x] && s[x] < s[y]))
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        return  1;
    }
};

int n, m;
int x[100005];
int y[100005];
int w[100005];
vector<pii> mp[N];

void calc(vector<Ques>  qr) {
    iota(DSU::p + 1,DSU::p + 1 + n,1);
    fill(DSU::s + 1,DSU::s + 1 + n,1);
    vector<Ques>    sta;
    vector<Edge>    E;
    vector<int>     vx;
    vector<int>     ed;
    for(Ques t : qr)    {
        if(!t.idx)  uE[t.ver] = 1,  uV[x[t.ver]] = uV[y[t.ver]] = 1;
        else        sta.pb(t),      uV[t.ver] = 1;
    }
    for(int i = 1 ; i <= n ; ++i)   if (uV[i])  vx.pb(i);
    for(int i = 1 ; i <= m ; ++i)   if (uE[i])  ed.pb(i);
    for(int i = 1 ; i <= m ; ++i)   E.pb({x[i],y[i],w[i],i});
    sort(all(E));
    sort(all(sta));
    int ptr = 0;
    for(Ques t : sta)   {
        while (ptr < sz(E) && E[ptr].w >= t.mas)    {
            if(!uE[E[ptr].i])   DSU::join(E[ptr].x,E[ptr].y);
            ptr++;
        }
        for(int x : vx) mp[t.idx].pb(pii(x,{DSU::lead(x),DSU::s[DSU::p[x]]}));
    }
    for(Ques q : qr)    {
        if(!q.idx)  {   w[q.ver] = q.mas;   continue;   }
        for(pii t : mp[q.idx])  DSU::p[t.X] = t.Y.X, DSU::s[t.X] = t.Y.Y;
        for(int i : ed) if (w[i] >= q.mas)
            DSU::join(x[i],y[i]);
        printf("%d\n",DSU::s[DSU::lead(q.ver)]);
    }
    for(int x : vx) uV[x] = 0, mp[x].clear();
    for(int x : ed) uE[x] = 0;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    scanf("%d%d",&n,&m);

    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d",&x[i],&y[i],&w[i]);

    int q;  scanf("%d",&q);

    vector<Ques>    v;

    for(int i = 1 ; i <= q ; ++i)   {
        int t, x, y;
        scanf("%d%d%d",&t,&x,&y);
        if (t == 1) v.pb({y,x,0});
        if (t == 2) v.pb({y,x,i});
    }

    for(int i = 0 ; i < q ; i += B)
        calc(vector<Ques>(v.begin() + i,v.begin() + min((int)v.size(),i + B)));
}

Compilation message (stderr)

bridges.cpp: In function 'void calc(std::vector<Ques>)':
bridges.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptr < sz(E) && E[ptr].w >= t.mas)    {
                    ^
bridges.cpp: In function 'int main()':
bridges.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x[i],&y[i],&w[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int q;  scanf("%d",&q);
             ~~~~~^~~~~~~~~
bridges.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&t,&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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