Submission #140649

#	Time	Username	Problem	Language	Result	Execution time	Memory
140649		HellAngel	Bridges (APIO19_bridges)	C++14	59 / 100	3039 ms	18980 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
 
const int ahjhj =230;
const int maxn = 100007;
 
int n, m,u[maxn], v[maxn], d[maxn], q, type[maxn], a[maxn], b[maxn], d2[maxn];
int lab[maxn], fakelab[maxn], ans[maxn], visited[maxn], kq, cur;
int Change[maxn], nChange, thua[maxn], nthua, id[maxn], newid[maxn], nnewid;
int Find(int x)
{
    if(lab[x] < 0) return x;
    return lab[x] = Find(lab[x]);
}
 
void Union(int x, int y)
{
    if(lab[x] > lab[y]) swap(x, y);
    lab[x] += lab[y];
    lab[y] = x;
}
 
vector<int> qr[2][maxn], vt[maxn], Edge[maxn];
 
int BS(int type, int pos)
{
    int l = 0;
    int r = (int)vt[type].size() - 1;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(vt[type][mid] > pos) r = mid - 1;
        else l = mid + 1;
    }
    if(r == -1) return r;
    return vt[type][r];
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("Test.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> d[i];
        id[i] = i;
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> type[i] >> a[i] >> b[i];
        ans[i] = -1;
        qr[type[i] - 1][i / ahjhj].push_back(i);
        if(type[i] == 1) vt[a[i]].push_back(i);
    }
    sort(id + 1, id + m + 1, [](const int &a, const int &b){return d[a] > d[b];});
    for(int cnt = 0; cnt <= q / ahjhj; cnt++)
    {
        for(int i = 1; i <= n; i++) lab[i] = -1;
        sort(qr[1][cnt].begin(), qr[1][cnt].end(), [](const int &u, const int &v){return b[u] > b[v];});
        int cur = 1;
        for(auto i: qr[0][cnt]) if(!d2[a[i]]) d2[a[i]] = 1, Change[++nChange] = a[i];
        for(auto i: qr[1][cnt])
        {
            while(cur <= m)
            {
                if(d2[id[cur]])
                {
                    cur++;
                }
                else
                if(d[id[cur]] >= b[i])
                {
                    if(Find(u[id[cur]]) != Find(v[id[cur]]))
                    Union(Find(u[id[cur]]), Find(v[id[cur]]));
                    cur++;
                }
                else break;
            }
            for(int k = 1; k <= nChange; k++)
            {
                int j = Change[k];
                int gau = BS(j, i);
                int haha;
                if(gau == -1) haha = d[j];
                else haha = b[gau];
                if(haha >= b[i])
                {
                    if(Find(u[j]) != Find(v[j]))
                    {
                        if(Edge[Find(u[j])].size() == 0) thua[++nthua] = Find(u[j]);
                        if(Edge[Find(v[j])].size() == 0) thua[++nthua] = Find(v[j]);
                        Edge[Find(u[j])].push_back(Find(v[j]));
                        Edge[Find(v[j])].push_back(Find(u[j]));
                    }
                }
            }
            thua[++nthua] = Find(a[i]);
            kq = 0;
            queue<int> q;
            q.push(Find(a[i]));
            visited[Find(a[i])] = 1;
            while(!q.empty())
            {
                int gau = q.front();
                kq += -lab[gau];
                q.pop();
                for(auto v: Edge[gau])
                {
                    if(!visited[v])
                    {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            ans[i] = kq;
            for(int i = 1; i <= nthua; i++) Edge[thua[i]] = {}, visited[thua[i]] = 0;
            nthua = 0;
        }
        for(auto i: qr[0][cnt]) d[a[i]] = b[i];
        sort(Change + 1, Change + nChange + 1, [](const int &a, const int &b){return d[a] < d[b];});
        for(int i = 1; i <= m; i++)
        {
            if(d2[id[i]]) continue;
            if(nChange > 0 && d[Change[nChange]] > d[id[i]]) newid[++nnewid] = Change[nChange--], i--;
            //if(Change.size() && d[Change.back()] > d[id[i]]) newid.push_back(Change.back()), Change.pop_back(), i--;
            else newid[++nnewid] = id[i];
        }
        while(nChange > 0) newid[++nnewid] = Change[nChange--];
        for(int i = 1; i <= m; i++) id[i] = newid[i];
        nnewid = 0;
        for(auto i: qr[0][cnt]) d2[a[i]] = 0;
    }
    for(int i = 1; i <= q; i++) if(~ans[i]) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int BS(int, int)':
bridges.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:43:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("Test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:43:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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