답안 #411466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411466	2021-05-25T11:23:41 Z	mhy908	Collapse (JOI18_collapse)	C++14	컴파일 오류	0 ms	0 KB

collapse

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

const int BUC=300;

struct UNION_FIND{
    int par[100010], sz[100010], cnt;
    vector<int> vc;
    void init(int num){for(int i=1; i<=num; i++)par[i]=i, sz[i]=1; cnt=0;}
    int findpar(int num){return num==par[num]?num:findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a);
        b=findpar(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a, b);
        vc.eb(b);
        par[b]=a;
        sz[a]+=sz[b];
        cnt++;
    }
    void rollback(){
        int tmp=vc.back();
        vc.pop_back();
        sz[par[tmp]]-=sz[tmp];
        par[tmp]=tmp;
        cnt--;
    }
}uf;

int n, m, q, query[100010], ans[100010];
pair<int, pii> edge[100010];
vector<int> qlst[100010];

bool cmpl(pii a, pii b){return a.S<b.S;}
bool cmpr(pii a, pii b){return a.F>b.F;}

void solve(int s, int e){

    set<pii> edgs;
    for(int i=1; i<s; i++){
        if(edge[i].F==0)edgs.insert(edge[i].S);
        else edgs.erase(edge[i].S);
    }
    vector<pii> org;
    for(int i=s; i<=e; i++){
        if(edge[i].F&&edgs.find(edge[i].S)!=edgs.end()){
            edgs.erase(edge[i].S);
            org.eb(edge[i].S);
        }
    }

    vector<pair<int, pii> > nq;
    for(int i=s; i<=e; i++){
        for(auto j:qlst[i])nq.eb(query[j], mp(i, j));
    }

    vector<pii> nedge;
    for(auto i:edgs)nedge.eb(i);

    sort(all(nedge), cmpl);
    sort(all(nq));
    uf.init(n);

    int pv=0;
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].S>i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.S<=i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

    sort(all(nedge), cmpr);
    reverse(all(nq));
    uf.init(n);
    pv=0;
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].F<=i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.F>i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=n-i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &edge[i].F, &edge[i].S.F, &edge[i].S.S);
        if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
        edge[i].S.F++, edge[i].S.S++;
    }
    for(int i=1; i<=q; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        qlst[a+1].eb(i);
        query[i]=b+1;
    }

    for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
    for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}

Compilation message

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:99:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~
collapse.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:127:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~
collapse.cpp: In function 'int main()':
collapse.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf("%d %d %d", &edge[i].F, &edge[i].S.F, &edge[i].S.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccx28aYP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccI5kmCP.o:collapse.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccx28aYP.o: in function `main':
grader.cpp:(.text.startup+0x227): undefined reference to `simulateCollapse(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status