Submission #170109

#	Time	Username	Problem	Language	Result	Execution time	Memory
170109		arnold518	Bridges (APIO19_bridges)	C++14	100 / 100	2766 ms	12360 KiB

bridges

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct Edge
{
    int u, v, w, idx;
    bool operator < (const Edge &p) const { return w>p.w; }
};

struct Query
{
    int t, u, w, idx;
    bool operator < (const Query &p) const { return w>p.w; }
};

int N, M, Q, SQ=1000;
int t[MAXN+10];
Edge edge[MAXN+10];
Query query[MAXN+10];

vector<int> S;
int Par[MAXN+10], Rank[MAXN+10];
vector<pii> ans;

void init()
{
    S.clear();
    for(int i=1; i<=N; i++) Par[i]=i, Rank[i]=1;
}

int cnt=0;

int Find(int x) { return x==Par[x] ? x : Find(Par[x]); }

void Union(int x, int y)
{
    x=Find(x); y=Find(y);
    if(x==y) return;
    if(Rank[x]<Rank[y]) swap(x, y);
    Rank[x]+=Rank[y];
    Par[y]=x;
    S.push_back(y);
    cnt++;
    //printf("UNION %d %d\n", x, y);
}

void Restore()
{
    if(S.empty()) return;
    //printf("RESTORE %d %d\n", S.back(), Par[S.back()]);
    Rank[Par[S.back()]]-=Rank[S.back()];
    Par[S.back()]=S.back();
    S.pop_back();
}

int main()
{
    int i, j, k, p;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].idx=i;
        if(edge[i].u>edge[i].v) swap(edge[i].u, edge[i].v);
    }
    scanf("%d", &Q);
    for(i=1; i<=Q; i++) scanf("%d%d%d", &query[i].t, &query[i].u, &query[i].w), query[i].idx=i;

    vector<Edge> E;
    for(i=1; i<=M; i++) E.push_back(edge[i]);
    sort(E.begin(), E.end());

    for(i=0; i<=Q/SQ; i++)
    {
        int s=max(1, i*SQ), e=min(Q, i*SQ+SQ-1);
        init();

        //printf("============\n");
        //for(auto it : E) printf("%d %d %d\n", it.u, it.v, it.w);
        //printf("============\n");

        vector<Edge> E1, E2;

        vector<Query> up, qu;
        vector<int> up2;
        for(j=s; j<=e; j++)
        {
            if(query[j].t==1) up.push_back(query[j]), up2.push_back(query[j].u);
            else qu.push_back(query[j]);
        }

        sort(up2.begin(), up2.end());
        up2.erase(unique(up2.begin(), up2.end()), up2.end());
        sort(qu.begin(), qu.end());

        for(j=0; j<E.size(); j++) if(!binary_search(up2.begin(), up2.end(), E[j].idx)) E1.push_back(E[j]);

        for(j=0, k=0; j<qu.size(); j++)
        {
            //printf("!!!!!!!!!!QUERY SOLVING %d %d!!!!!!!\n", qu[j].u, qu[j].w);
            for(; k<E.size() && E[k].w>=qu[j].w; k++)
            {
                if(binary_search(up2.begin(), up2.end(), E[k].idx)) continue;
                //printf("!%d %d\n", E[k].u, E[k].v);
                Union(E[k].u, E[k].v);
            }

            cnt=0;

            for(p=0; p<up2.size(); p++) t[up2[p]]=edge[up2[p]].w;
            for(p=0; p<up.size() && up[p].idx<qu[j].idx; p++) t[up[p].u]=up[p].w;
            for(p=0; p<up2.size(); p++) if(t[up2[p]]>=qu[j].w) Union(edge[up2[p]].u, edge[up2[p]].v);
            ans.push_back({qu[j].idx, Rank[Find(qu[j].u)]});
            while(cnt--) Restore();
        }

        //printf("!%d %d %d\n", E.size(), E1.size(), E2.size());

        for(p=0; p<up.size(); p++) edge[up[p].u].w=up[p].w;
        for(p=0; p<up2.size(); p++) E2.push_back(edge[up2[p]]);

        if(E1.size()+E2.size()!=M) while(1);

        sort(E2.begin(), E2.end());
        E.clear(); E.resize(M);
        merge(E1.begin(), E1.end(), E2.begin(), E2.end(), E.begin());
    }

    sort(ans.begin(), ans.end());
    for(auto it : ans) printf("%d\n", it.second);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<E.size(); j++) if(!binary_search(up2.begin(), up2.end(), E[j].idx)) E1.push_back(E[j]);
                  ~^~~~~~~~~
bridges.cpp:104:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0, k=0; j<qu.size(); j++)
                       ~^~~~~~~~~~
bridges.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; k<E.size() && E[k].w>=qu[j].w; k++)
                   ~^~~~~~~~~
bridges.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up2.size(); p++) t[up2[p]]=edge[up2[p]].w;
                      ~^~~~~~~~~~~
bridges.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up.size() && up[p].idx<qu[j].idx; p++) t[up[p].u]=up[p].w;
                      ~^~~~~~~~~~
bridges.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up2.size(); p++) if(t[up2[p]]>=qu[j].w) Union(edge[up2[p]].u, edge[up2[p]].v);
                      ~^~~~~~~~~~~
bridges.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(p=0; p<up.size(); p++) edge[up[p].u].w=up[p].w;
                  ~^~~~~~~~~~
bridges.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(p=0; p<up2.size(); p++) E2.push_back(edge[up2[p]]);
                  ~^~~~~~~~~~~
bridges.cpp:128:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(E1.size()+E2.size()!=M) while(1);
            ~~~~~~~~~~~~~~~~~~~^~~
bridges.cpp:66: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:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].idx=i;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
bridges.cpp:73:79: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=Q; i++) scanf("%d%d%d", &query[i].t, &query[i].u, &query[i].w), query[i].idx=i;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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