oj.uz

Submission #67480

# Submission time Handle Problem Language Result Execution time Memory
67480 2018-08-14T10:35:58 Z top34051 Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 230148 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 term[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];
map<pii,int> last;

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);
    }
    for(int i=0;i<edge[pos].size();i++) dsu.pop_edge();
}

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};
        if(T[i]==0) {
            last[{u,v}] = i;
            term[i] = m-1;
        }
        else {
            term[last[{u,v}]] = i-1;
        }
    }
    for(int i=0;i<q;++i) day[i] = W[i];

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

    //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[t]==1) continue;
                    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];
            if(T[x]==1) continue;
            update(1,0,m-1,x,term[x],p[x]);
        }
    }

//    printf("-----------------------\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[t]==1) continue;
                    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];
            if(T[x]==1) continue;
            update(1,0,m-1,x,term[x],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:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<topping[x].size();++i) dsu.pop_edge();
                         ~^~~~~~~~~~~~~~~~~~
collapse.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edge[pos].size();i++) dsu.pop_edge();
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17272 KB Output is correct
2 Incorrect 20 ms 17272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 19904 KB Output is correct
2 Incorrect 74 ms 23472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 23472 KB Output is correct
2 Correct 86 ms 24100 KB Output is correct
3 Correct 166 ms 28544 KB Output is correct
4 Correct 211 ms 36288 KB Output is correct
5 Correct 845 ms 184640 KB Output is correct
6 Correct 1213 ms 196240 KB Output is correct
7 Correct 6051 ms 225692 KB Output is correct
8 Correct 10666 ms 230096 KB Output is correct
9 Correct 60 ms 230096 KB Output is correct
10 Correct 998 ms 230096 KB Output is correct
11 Correct 14153 ms 230096 KB Output is correct
12 Execution timed out 15110 ms 230148 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17272 KB Output is correct
2 Incorrect 20 ms 17272 KB Output isn't correct
3 Halted 0 ms 0 KB -