답안 #67532 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67532	2018-08-14T17:54:08 Z	top34051	Collapse (JOI18_collapse)	C++17	5 / 100	15000 ms	191792 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);
    }

    dsu.init(n);

    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]);
            }
        }
        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);
    }

    dsu.init(n);

    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]);
            }
        }
        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	29 ms	17272 KB	Output is correct
2	Correct	25 ms	17272 KB	Output is correct
3	Correct	28 ms	17792 KB	Output is correct
4	Correct	31 ms	18156 KB	Output is correct
5	Correct	38 ms	18156 KB	Output is correct
6	Correct	84 ms	24320 KB	Output is correct
7	Correct	23 ms	24320 KB	Output is correct
8	Correct	19 ms	24320 KB	Output is correct
9	Correct	47 ms	24320 KB	Output is correct
10	Correct	61 ms	24320 KB	Output is correct
11	Correct	90 ms	25236 KB	Output is correct
12	Correct	77 ms	25236 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	25236 KB	Output is correct
2	Correct	65 ms	25236 KB	Output is correct
3	Correct	7226 ms	35796 KB	Output is correct
4	Correct	192 ms	38092 KB	Output is correct
5	Correct	11065 ms	39156 KB	Output is correct
6	Correct	856 ms	162868 KB	Output is correct
7	Correct	14011 ms	191792 KB	Output is correct
8	Correct	9112 ms	191792 KB	Output is correct
9	Correct	85 ms	191792 KB	Output is correct
10	Correct	125 ms	191792 KB	Output is correct
11	Correct	590 ms	191792 KB	Output is correct
12	Correct	10078 ms	191792 KB	Output is correct
13	Execution timed out	15065 ms	191792 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	191792 KB	Output is correct
2	Correct	88 ms	191792 KB	Output is correct
3	Correct	130 ms	191792 KB	Output is correct
4	Correct	246 ms	191792 KB	Output is correct
5	Correct	583 ms	191792 KB	Output is correct
6	Correct	862 ms	191792 KB	Output is correct
7	Correct	8057 ms	191792 KB	Output is correct
8	Execution timed out	15061 ms	191792 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	17272 KB	Output is correct
2	Correct	25 ms	17272 KB	Output is correct
3	Correct	28 ms	17792 KB	Output is correct
4	Correct	31 ms	18156 KB	Output is correct
5	Correct	38 ms	18156 KB	Output is correct
6	Correct	84 ms	24320 KB	Output is correct
7	Correct	23 ms	24320 KB	Output is correct
8	Correct	19 ms	24320 KB	Output is correct
9	Correct	47 ms	24320 KB	Output is correct
10	Correct	61 ms	24320 KB	Output is correct
11	Correct	90 ms	25236 KB	Output is correct
12	Correct	77 ms	25236 KB	Output is correct
13	Correct	45 ms	25236 KB	Output is correct
14	Correct	65 ms	25236 KB	Output is correct
15	Correct	7226 ms	35796 KB	Output is correct
16	Correct	192 ms	38092 KB	Output is correct
17	Correct	11065 ms	39156 KB	Output is correct
18	Correct	856 ms	162868 KB	Output is correct
19	Correct	14011 ms	191792 KB	Output is correct
20	Correct	9112 ms	191792 KB	Output is correct
21	Correct	85 ms	191792 KB	Output is correct
22	Correct	125 ms	191792 KB	Output is correct
23	Correct	590 ms	191792 KB	Output is correct
24	Correct	10078 ms	191792 KB	Output is correct
25	Execution timed out	15065 ms	191792 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

답안 #67532

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