답안 #67489 :: oj.uz

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

collapse

//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);
//            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:95: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:103: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	23 ms	17320 KB	Output is correct
2	Correct	24 ms	17320 KB	Output is correct
3	Correct	24 ms	17532 KB	Output is correct
4	Correct	25 ms	18092 KB	Output is correct
5	Correct	39 ms	18092 KB	Output is correct
6	Correct	82 ms	27140 KB	Output is correct
7	Correct	22 ms	27140 KB	Output is correct
8	Correct	21 ms	27140 KB	Output is correct
9	Correct	50 ms	27140 KB	Output is correct
10	Correct	64 ms	27140 KB	Output is correct
11	Correct	87 ms	28140 KB	Output is correct
12	Correct	101 ms	28140 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	28140 KB	Output is correct
2	Correct	55 ms	28140 KB	Output is correct
3	Correct	5000 ms	35668 KB	Output is correct
4	Correct	211 ms	37652 KB	Output is correct
5	Correct	7497 ms	38884 KB	Output is correct
6	Correct	1594 ms	261696 KB	Output is correct
7	Correct	9272 ms	261696 KB	Output is correct
8	Correct	6035 ms	261696 KB	Output is correct
9	Correct	57 ms	261696 KB	Output is correct
10	Correct	91 ms	261696 KB	Output is correct
11	Correct	447 ms	261696 KB	Output is correct
12	Correct	6717 ms	261696 KB	Output is correct
13	Correct	11906 ms	261696 KB	Output is correct
14	Execution timed out	15088 ms	299968 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	299968 KB	Output is correct
2	Correct	113 ms	299968 KB	Output is correct
3	Correct	139 ms	299968 KB	Output is correct
4	Correct	247 ms	299968 KB	Output is correct
5	Correct	958 ms	299968 KB	Output is correct
6	Correct	1205 ms	299968 KB	Output is correct
7	Correct	6531 ms	299968 KB	Output is correct
8	Correct	12130 ms	299968 KB	Output is correct
9	Correct	81 ms	299968 KB	Output is correct
10	Correct	1092 ms	299968 KB	Output is correct
11	Correct	13574 ms	299968 KB	Output is correct
12	Execution timed out	15101 ms	299968 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	17320 KB	Output is correct
2	Correct	24 ms	17320 KB	Output is correct
3	Correct	24 ms	17532 KB	Output is correct
4	Correct	25 ms	18092 KB	Output is correct
5	Correct	39 ms	18092 KB	Output is correct
6	Correct	82 ms	27140 KB	Output is correct
7	Correct	22 ms	27140 KB	Output is correct
8	Correct	21 ms	27140 KB	Output is correct
9	Correct	50 ms	27140 KB	Output is correct
10	Correct	64 ms	27140 KB	Output is correct
11	Correct	87 ms	28140 KB	Output is correct
12	Correct	101 ms	28140 KB	Output is correct
13	Correct	46 ms	28140 KB	Output is correct
14	Correct	55 ms	28140 KB	Output is correct
15	Correct	5000 ms	35668 KB	Output is correct
16	Correct	211 ms	37652 KB	Output is correct
17	Correct	7497 ms	38884 KB	Output is correct
18	Correct	1594 ms	261696 KB	Output is correct
19	Correct	9272 ms	261696 KB	Output is correct
20	Correct	6035 ms	261696 KB	Output is correct
21	Correct	57 ms	261696 KB	Output is correct
22	Correct	91 ms	261696 KB	Output is correct
23	Correct	447 ms	261696 KB	Output is correct
24	Correct	6717 ms	261696 KB	Output is correct
25	Correct	11906 ms	261696 KB	Output is correct
26	Execution timed out	15088 ms	299968 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

답안 #67489

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