답안 #67493 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67493	2018-08-14T10:59:01 Z	top34051	Collapse (JOI18_collapse)	C++14	5 / 100	15000 ms	154040 KB

collapse

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #67493

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 30.0

Subtask #3 0 / 30.0

Subtask #4 0 / 35.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 30.0

Subtask #3
0 / 30.0

Subtask #4
0 / 35.0