답안 #67497 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67497	2018-08-14T11:11:16 Z	top34051	Collapse (JOI18_collapse)	C++17	5 / 100	15000 ms	187944 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 = 330;

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++) {
        int st = id*sq, ft = min(m,id*sq+sq);
        //query
        for(int i=st;i<ft;++i) {
            for(auto x : wait[i]) {
                for(int j=st;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=st;i<ft;++i) {
            for(auto x : wait[i]) ask[day[x]].clear();
        }
        //updates
        for(int i=st;i<ft;++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);
        int st = id*sq, ft = min(m,id*sq+sq);
        //query
        for(int i=st;i<ft;++i) {
            for(auto x : wait[i]) {
                for(int j=st;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=st;i<ft;++i) {
            for(auto x : wait[i]) ask[day[x]].clear();
        }
        //updates
        for(int i=st;i<ft;++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	26 ms	17272 KB	Output is correct
2	Correct	19 ms	17272 KB	Output is correct
3	Correct	20 ms	17476 KB	Output is correct
4	Correct	23 ms	17880 KB	Output is correct
5	Correct	38 ms	17880 KB	Output is correct
6	Correct	70 ms	24152 KB	Output is correct
7	Correct	18 ms	24152 KB	Output is correct
8	Correct	22 ms	24152 KB	Output is correct
9	Correct	41 ms	24152 KB	Output is correct
10	Correct	61 ms	24152 KB	Output is correct
11	Correct	86 ms	24584 KB	Output is correct
12	Correct	78 ms	24584 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	24584 KB	Output is correct
2	Correct	54 ms	24584 KB	Output is correct
3	Correct	7833 ms	32892 KB	Output is correct
4	Correct	170 ms	34852 KB	Output is correct
5	Correct	10494 ms	35192 KB	Output is correct
6	Correct	792 ms	159088 KB	Output is correct
7	Correct	13235 ms	187944 KB	Output is correct
8	Correct	10167 ms	187944 KB	Output is correct
9	Correct	58 ms	187944 KB	Output is correct
10	Correct	129 ms	187944 KB	Output is correct
11	Correct	673 ms	187944 KB	Output is correct
12	Correct	10020 ms	187944 KB	Output is correct
13	Execution timed out	15044 ms	187944 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	187944 KB	Output is correct
2	Correct	78 ms	187944 KB	Output is correct
3	Correct	133 ms	187944 KB	Output is correct
4	Correct	187 ms	187944 KB	Output is correct
5	Correct	538 ms	187944 KB	Output is correct
6	Correct	754 ms	187944 KB	Output is correct
7	Correct	7342 ms	187944 KB	Output is correct
8	Execution timed out	15106 ms	187944 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	17272 KB	Output is correct
2	Correct	19 ms	17272 KB	Output is correct
3	Correct	20 ms	17476 KB	Output is correct
4	Correct	23 ms	17880 KB	Output is correct
5	Correct	38 ms	17880 KB	Output is correct
6	Correct	70 ms	24152 KB	Output is correct
7	Correct	18 ms	24152 KB	Output is correct
8	Correct	22 ms	24152 KB	Output is correct
9	Correct	41 ms	24152 KB	Output is correct
10	Correct	61 ms	24152 KB	Output is correct
11	Correct	86 ms	24584 KB	Output is correct
12	Correct	78 ms	24584 KB	Output is correct
13	Correct	51 ms	24584 KB	Output is correct
14	Correct	54 ms	24584 KB	Output is correct
15	Correct	7833 ms	32892 KB	Output is correct
16	Correct	170 ms	34852 KB	Output is correct
17	Correct	10494 ms	35192 KB	Output is correct
18	Correct	792 ms	159088 KB	Output is correct
19	Correct	13235 ms	187944 KB	Output is correct
20	Correct	10167 ms	187944 KB	Output is correct
21	Correct	58 ms	187944 KB	Output is correct
22	Correct	129 ms	187944 KB	Output is correct
23	Correct	673 ms	187944 KB	Output is correct
24	Correct	10020 ms	187944 KB	Output is correct
25	Execution timed out	15044 ms	187944 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

답안 #67497

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