답안 #67468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67468 2018-08-14T10:20:33 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
14065 ms 231820 KB
//S3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 500;

class dsu_type{
    public:
        int n, com;
        int head[maxn], sz[maxn];
        stack<pii> stk;
        int findhead(int x) {
            if(x==head[x]) return x;
            return findhead(head[x]);
        }
        void init(int _n) {
            n = com = _n;
            for(int i=0;i<n;i++) {
                head[i] = i;
                sz[i] = 1;
            }
            while(!stk.empty()) stk.pop();
        }
        void add_edge(int u, int v) {
            int x = findhead(u), y = findhead(v);
            if(sz[x] > sz[y]) swap(x,y);
            stk.push({x,y});
            if(x!=y) {
                head[x] = y;
                sz[y] += sz[x];
                com--;
            }
        }
        void pop_edge() {
            int x = stk.top().X, y = stk.top().Y; stk.pop();
            if(x!=y) {
                head[x] = x;
                sz[y] -= sz[x];
                com++;
            }
        }
        int getcom() {
            return com;
        }
} dsu;

int n,m,q;
pii p[maxn];
int day[maxn];
vector<int> ask[maxn];
vector<pii> edge[maxn*4];
int ord[maxn];
vector<int> wait[maxn];
vector<pii> topping[maxn];
int res[maxn];

void build(int pos, int l, int r) {
    if(l>r) return ;
    edge[pos].clear();
    if(l==r) return ;
    int mid = (l+r)/2;
    build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
}

void update(int pos, int l, int r, int x, int y, pii val) {
    if(l>r || r<x || y<l) return ;
    if(x<=l && r<=y) {
        edge[pos].push_back(val);
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,y,val);
    update(pos<<1|1,mid+1,r,x,y,val);
}

void solve(int pos, int l, int r) {
    for(auto t : edge[pos]) dsu.add_edge(t.X,t.Y);
    if(l==r) {
        for(auto x : ask[l]) {
//            printf("solve t = %d\n",l);
            for(auto t : topping[x]) {
                dsu.add_edge(t.X,t.Y);
            }
            res[x] += dsu.getcom();
            for(int i=0;i<topping[x].size();i++) dsu.pop_edge();
        }
    }
    else {
        int mid = (l+r)/2;
        solve(pos<<1,l,mid);
        solve(pos<<1|1,mid+1,r);
    }
}

bool cmpY(int x, int y) {
    return p[x].Y < p[y].Y;
}

bool cmpX(int x, int y) {
    return p[x].X > p[y].X;
}

std::vector<int> simulateCollapse(
    int N,
    std::vector<int> T,
    std::vector<int> X,
    std::vector<int> Y,
    std::vector<int> W,
    std::vector<int> P
) {
    n = N; m = T.size(); q = W.size();
    for(int i=0;i<m;i++) {
        int u = X[i], v = Y[i];
        if(u>v) swap(u,v);
        p[i] = {u,v};
    }
    for(int i=0;i<q;i++) day[i] = W[i];

    for(int i=0;i<m;i++) ord[i] = i;

    dsu.init(n);

    //solve L
    sort(&ord[0],&ord[m],cmpY);
//    for(int i=0;i<m;i++) printf("\t%d %d : %d\n",p[ord[i]].X,p[ord[i]].Y,ord[i]);

    build(1,0,m-1);

    for(int i=0;i<m;i++) wait[i].clear();
    for(int i=0;i<q;i++) {
        int l = 0, r = m-1, mid, pos = -1;
        while(l<=r) {
            mid = (l+r)/2;
            if(p[ord[mid]].Y <= P[i]) {
                pos = mid;
                l = mid+1;
            }
            else r = mid-1;
        }
        if(pos!=-1) wait[pos].push_back(i);
        else res[i] += n;
//        printf("wait %d = %d\n",i,pos);
    }

    for(int i=0;i<q;i++) topping[i].clear();
    for(int id=0;id*sq<m;id++) {
        //query
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            for(auto x : wait[i]) {
                for(int j=id*sq;j<=i;j++) {
                    int t = ord[j];
                    if(t <= day[x]) topping[x].push_back(p[t]);
                }
                ask[day[x]].push_back(x);
//                printf("\task %d at %d\n",x,day[x]);
            }
        }
        dsu.init(n);
        solve(1,0,m-1);
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            for(auto x : wait[i]) ask[day[x]].clear();
        }
        //updates
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            int x = ord[i];
            update(1,0,m-1,x,m-1,p[x]);
        }
    }

//    printf("-----------------------\n");

    dsu.init(n);

    //solve R
    sort(&ord[0],&ord[m],cmpX);
//    for(int i=0;i<m;i++) printf("\t%d %d : %d\n",p[ord[i]].X,p[ord[i]].Y,ord[i]);

    build(1,0,m-1);

    for(int i=0;i<m;i++) wait[i].clear();
    for(int i=0;i<q;i++) {
        int l = 0, r = m-1, mid, pos = -1;
        while(l<=r) {
            mid = (l+r)/2;
            if(p[ord[mid]].X > P[i]) {
                pos = mid;
                l = mid+1;
            }
            else r = mid-1;
        }
        if(pos!=-1) wait[pos].push_back(i);
        else res[i] += n;
//        printf("wait %d = %d\n",i,pos);
    }

    for(int i=0;i<q;i++) topping[i].clear();
    for(int id=0;id*sq<m;id++) {
//        printf("id = %d\n",id);
        //query
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            for(auto x : wait[i]) {
                for(int j=id*sq;j<=i;j++) {
                    int t = ord[j];
                    if(t <= day[x]) topping[x].push_back(p[t]);
                }
                ask[day[x]].push_back(x);
//                printf("\task %d at %d\n",x,day[x]);
            }
        }
        dsu.init(n);
        solve(1,0,m-1);
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            for(auto x : wait[i]) ask[day[x]].clear();
        }
        //updates
        for(int i=id*sq;i<min(m,id*sq+sq);i++) {
            int x = ord[i];
            update(1,0,m-1,x,m-1,p[x]);
        }
    }

    vector<int> vec;
    for(int i=0;i<q;i++) vec.push_back(res[i]-n);
    return vec;
}

Compilation message

collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<topping[x].size();i++) dsu.pop_edge();
                         ~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 17784 KB Output is correct
2 Incorrect 23 ms 17784 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 19908 KB Output is correct
2 Incorrect 61 ms 23748 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 23748 KB Output is correct
2 Correct 73 ms 24088 KB Output is correct
3 Correct 152 ms 28460 KB Output is correct
4 Correct 182 ms 36120 KB Output is correct
5 Correct 844 ms 184720 KB Output is correct
6 Correct 1016 ms 196216 KB Output is correct
7 Correct 6716 ms 226028 KB Output is correct
8 Correct 12123 ms 230768 KB Output is correct
9 Correct 63 ms 230768 KB Output is correct
10 Correct 971 ms 230768 KB Output is correct
11 Correct 11748 ms 230768 KB Output is correct
12 Correct 13172 ms 230768 KB Output is correct
13 Correct 11738 ms 231820 KB Output is correct
14 Correct 14065 ms 231820 KB Output is correct
15 Correct 11690 ms 231820 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 17784 KB Output is correct
2 Incorrect 23 ms 17784 KB Output isn't correct
3 Halted 0 ms 0 KB -