Submission #90118

#	Time	Username	Problem	Language	Result	Execution time	Memory
90118		cs71107	간선 파괴 (GA5_destroy)	C++14	100 / 100	68 ms	22752 KiB

destroy

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

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
const int INF = 1e9+1;
const int MAXN = 2e5+10;
const int MAXM = 7e2+10;
priority_queue<int> pq;

int par[MAXN];
int par1[MAXN];
pii edge[MAXN];
int L[MAXN];
int R[MAXN];

int mst[MAXM];
int rvmst[MAXM];
int component[MAXM][MAXM];

void init(int V)
{
    for(int i=1;i<=V;i++)par[i] = i;
    return;
}

int root(int x)
{
    if(x==par[x])return x;
    else return par[x] = root(par[x]);
}

bool mymerge(int x,int y)
{

    x = root(x);
    y = root(y);

    if(x==y)return false;

    //if(x>y)swap(x,y);

    par[y] = x;

    return true;

}

int main()
{
    int V,E;
    int x,y;
    int mstcnt = 1;
    int rvmstcnt = 1;
    scanf("%d%d",&V,&E);

    init(V);

    for(int i=1;i<=E;i++)scanf("%d%d",&edge[i].first,&edge[i].second);

    for(int i=1;i<=E;i++){

        x = edge[i].first;
        y = edge[i].second;


        if(!mymerge(x,y))continue;

        mst[mstcnt++] = i;

    }

    init(V);

    for(int i=E;i>=1;i--){

        x = edge[i].first;
        y = edge[i].second;

        if(!mymerge(x,y))continue;

        rvmst[rvmstcnt++] = i;

    }

    init(V);

    int nw,rnw,x1,y1;

    for(int i=0;i<mstcnt;i++)
    {
        nw = mst[i];

        x = edge[nw].first;
        y = edge[nw].second;

        mymerge(x,y);
        component[i][0] = V-i;

        for(int j=1;j<=V;j++)par1[j] = par[j];

        for(int j=1;j<rvmstcnt;j++){

            rnw = rvmst[j];

            x1 = edge[rnw].first;
            y1 = edge[rnw].second;

            if(mymerge(x1,y1))component[i][j] = component[i][j-1]-1;
            else component[i][j] = component[i][j-1];

        }


        for(int j=1;j<=V;j++)par[j] = par1[j];
    }

    for(int i=1;i<mstcnt;i++)nw = mst[i], L[nw] = i;
    for(int i=1;i<rvmstcnt;i++)nw = rvmst[i], R[nw] = i;

    for(int i=1;i<=E;i++)L[i] = max(L[i],L[i-1]);
    for(int i=E;i>=1;i--)R[i] = max(R[i],R[i+1]);




    int q;

    scanf("%d",&q);

    int a,b;

    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&a,&b);

        printf("%d\n",component[L[a-1]][R[b+1]]);

    }


    return 0;
}

Compilation message (stderr)

destroy.cpp: In function 'int main()':
destroy.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&V,&E);
     ~~~~~^~~~~~~~~~~~~~
destroy.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=E;i++)scanf("%d%d",&edge[i].first,&edge[i].second);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
destroy.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
destroy.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40