oj.uz

Submission #67493

# Submission time Handle Problem Language Result Execution time Memory
67493 2018-08-14T10:59:01 Z top34051 Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 154040 KB 
#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 = 300;

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);
//            printf("\tadd edge %d %d\n",x,y);
            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();
//            printf("\tpop edge %d %d\n",x,y);
            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]) {
            for(auto t : topping[x]) {
//                printf("\tt %d : topping %d %d\n",l,t.X,t.Y);
                dsu.add_edge(t.X,t.Y);
            }
            res[x] += dsu.getcom();
//            printf("solve t = %d => %d\n",l,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++) printf("%d : %d %d\n",i,term[i],T[i]);

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

//    printf("-------------------\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[t]==1) continue;
                    if(t <= day[x] && day[x]<=term[t]) 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] && day[x] <= term[t]) 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:94: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:102: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17144 KB Output is correct
2 Correct 19 ms 17144 KB Output is correct
3 Correct 21 ms 17600 KB Output is correct
4 Correct 27 ms 17924 KB Output is correct
5 Correct 42 ms 17924 KB Output is correct
6 Correct 81 ms 23432 KB Output is correct
7 Correct 27 ms 23432 KB Output is correct
8 Correct 24 ms 23432 KB Output is correct
9 Correct 51 ms 23432 KB Output is correct
10 Correct 74 ms 23432 KB Output is correct
11 Correct 116 ms 23784 KB Output is correct
12 Correct 92 ms 23784 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 23784 KB Output is correct
2 Correct 61 ms 23784 KB Output is correct
3 Correct 8994 ms 32884 KB Output is correct
4 Correct 175 ms 34672 KB Output is correct
5 Correct 11743 ms 34672 KB Output is correct
6 Correct 635 ms 84828 KB Output is correct
7 Correct 13469 ms 145376 KB Output is correct
8 Correct 9805 ms 145376 KB Output is correct
9 Correct 65 ms 145376 KB Output is correct
10 Correct 112 ms 145376 KB Output is correct
11 Correct 706 ms 145376 KB Output is correct
12 Correct 11737 ms 145376 KB Output is correct
13 Execution timed out 15014 ms 145376 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 145376 KB Output is correct
2 Correct 69 ms 145376 KB Output is correct
3 Correct 120 ms 145376 KB Output is correct
4 Correct 194 ms 145376 KB Output is correct
5 Correct 586 ms 145376 KB Output is correct
6 Correct 763 ms 145376 KB Output is correct
7 Correct 8562 ms 151788 KB Output is correct
8 Execution timed out 15014 ms 154040 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17144 KB Output is correct
2 Correct 19 ms 17144 KB Output is correct
3 Correct 21 ms 17600 KB Output is correct
4 Correct 27 ms 17924 KB Output is correct
5 Correct 42 ms 17924 KB Output is correct
6 Correct 81 ms 23432 KB Output is correct
7 Correct 27 ms 23432 KB Output is correct
8 Correct 24 ms 23432 KB Output is correct
9 Correct 51 ms 23432 KB Output is correct
10 Correct 74 ms 23432 KB Output is correct
11 Correct 116 ms 23784 KB Output is correct
12 Correct 92 ms 23784 KB Output is correct
13 Correct 74 ms 23784 KB Output is correct
14 Correct 61 ms 23784 KB Output is correct
15 Correct 8994 ms 32884 KB Output is correct
16 Correct 175 ms 34672 KB Output is correct
17 Correct 11743 ms 34672 KB Output is correct
18 Correct 635 ms 84828 KB Output is correct
19 Correct 13469 ms 145376 KB Output is correct
20 Correct 9805 ms 145376 KB Output is correct
21 Correct 65 ms 145376 KB Output is correct
22 Correct 112 ms 145376 KB Output is correct
23 Correct 706 ms 145376 KB Output is correct
24 Correct 11737 ms 145376 KB Output is correct
25 Execution timed out 15014 ms 145376 KB Time limit exceeded
26 Halted 0 ms 0 KB -