답안 #67457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67457 2018-08-14T10:14:35 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
7258 ms 153860 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 = 320;

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) {
    for(int i=l;i<=r;i++) edge[i].clear();
}

void update(int pos, int l, int r, int x, int y, pii val) {
    edge[x].push_back(val);
}

void solve(int pos, int l, int r) {
    if(l==r) {
        for(auto t : edge[l]) dsu.add_edge(t.X,t.Y);
        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:79: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 24 ms 17404 KB Output is correct
2 Incorrect 20 ms 17404 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20032 KB Output is correct
2 Incorrect 71 ms 23920 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 23920 KB Output is correct
2 Correct 87 ms 24008 KB Output is correct
3 Correct 126 ms 28508 KB Output is correct
4 Correct 208 ms 36276 KB Output is correct
5 Correct 623 ms 114824 KB Output is correct
6 Correct 836 ms 138372 KB Output is correct
7 Correct 3564 ms 147992 KB Output is correct
8 Correct 5607 ms 151660 KB Output is correct
9 Correct 71 ms 151660 KB Output is correct
10 Correct 688 ms 151660 KB Output is correct
11 Correct 6021 ms 151660 KB Output is correct
12 Correct 7258 ms 153604 KB Output is correct
13 Correct 6346 ms 153604 KB Output is correct
14 Correct 6261 ms 153860 KB Output is correct
15 Correct 5847 ms 153860 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 17404 KB Output is correct
2 Incorrect 20 ms 17404 KB Output isn't correct
3 Halted 0 ms 0 KB -