제출 #410287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410287		doowey	Collapse (JOI18_collapse)	C++14	0 / 100	2534 ms	10936 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair



const int K = 5010;
const int N = (int)1e5 + 5;

int n;

bool active[N];
bool change[N];

struct query{
    int type;
    int time;
    int xx;
    int id;
    bool operator< (const query &qi) const {
        if(time == qi.time)
            return type < qi.type;
        return time < qi.time;
    }
};

int par[N];
int sub[N];

vector<pii> rev;

int fin(int x){
    if(par[x] == x) return x;
    return par[x]=fin(par[x]);
}

int total;

void unite(int u, int v, bool keep){
    u = fin(u);
    v = fin(v);
    if(u == v) return;
    total ++ ;
    if(sub[u] > sub[v]) swap(u, v);
    sub[v] += sub[u];
    par[u] = v;
    if(keep)
        rev.push_back(mp(u, v));
}

vector<int> simulateCollapse(int _N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
    n = _N;
    vector<query> qq;
    vector<pii> E;
    for(int i = 0 ; i < T.size(); i ++ ){
        if(X[i] > Y[i]) swap(X[i], Y[i]);
        E.push_back(mp(X[i], Y[i]));
    }
    sort(E.begin(), E.end());
    E.resize(unique(E.begin(), E.end()) - E.begin());
    int m = E.size();
    int id;
    for(int i = 0 ; i < X.size(); i ++ ){
        id = lower_bound(E.begin(), E.end(), mp(X[i], Y[i])) - E.begin();
        X[i] = id;
    }
    vector<query> qaq;
    for(int i = 0 ; i < T.size(); i ++ ){
        qaq.push_back({0, i, X[i], 0});
    }
    for(int i = 0 ; i < W.size(); i ++ ){
        qaq.push_back({1, W[i], P[i], i});
    }
    sort(qaq.begin(), qaq.end());
    vector<int> soln(W.size(), n);
    int li = 0;
    int ri;
    int pp;
    while(li < qaq.size()){
        ri = min((int)qaq.size() - 1, li + K - 1);
        for(int i = 0 ; i < m ; i ++ ){
            change[i] = false;
        }
        for(int i = 0 ; i < n; i ++ ){
            par[i] = i;
            sub[i] = 1;
        }
        for(int j = li ; j <= ri; j ++ ){
            if(qaq[j].type == 0){
                change[qaq[j].xx] = true;
            }
        }
        vector<pii> res;
        vector<int> chk;
        for(int i = 0 ; i < m ; i ++ ){
            if(change[i] == false && active[i]){
                res.push_back(mp(E[i].se, E[i].fi));
            }
            else{
                if(change[i]){
                    chk.push_back(i);
                }
            }
        }
        // !!!!!!!!!!!!!!!!!!!1
        sort(res.begin(), res.end());
        vector<pii> ord;
        for(int j = li ; j <= ri ;j ++ ){
            if(qaq[j].type == 1){
                ord.push_back(mp(qaq[j].xx, j));
            }
        }
        sort(ord.begin(), ord.end());
        pp = 0;
        total = 0;
        for(auto &x : ord){
            while(pp < res.size() && res[pp].fi <= x.fi){
                unite(res[pp].fi, res[pp].se, false);
                pp ++ ;
            }
            for(int j = li ; j < x.se; j ++ ){
                if(qaq[j].type == 0){
                    active[qaq[j].xx] ^= 1;
                }
            }
            for(auto y : chk){
                if(active[y] && E[y].se <= x.fi)
                    unite(E[y].fi, E[y].se, true);
            }
            soln[qaq[x.se].id] -= total;
            while(!rev.empty()){
                total -- ;
                sub[rev.back().se] -= sub[rev.back().fi];
                par[rev.back().fi] = rev.back().fi;
                rev.pop_back();
            }
            for(int j = li ; j < x.se; j ++ ){
                if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
            }
        }
        // #############################
        for(auto &x : res){
            swap(x.fi, x.se);
        }
        sort(res.begin(), res.end());
        reverse(res.begin(), res.end());
        reverse(ord.begin(), ord.end());
        for(int i = 0 ; i < n; i ++ ){
            par[i] = i;
            sub[i] = 1;
        }
        pp = 0;
        total = 0;
        for(auto x : ord){
            while(pp < res.size() && res[pp].fi > x.fi){
                unite(res[pp].fi, res[pp].se, false);
                pp ++ ;
            }
            for(int j = li ; j < x.se; j ++ ){
                if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
            }
            for(auto y : chk){
                if(active[y] && E[y].fi > x.fi)
                    unite(E[y].fi, E[y].se, true);
            }
            soln[qaq[x.se].id] -= total;
            while(!rev.empty()){
                total -- ;
                sub[rev.back().se] -= sub[rev.back().fi];
                par[rev.back().fi] = rev.back().fi;
                rev.pop_back();
            }
            for(int j = li ; j < x.se; j ++ ){
                if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
            }
        }
        // #############################
        for(int j = li; j <= ri; j ++ ){
            if(qaq[j].type == 0){
                active[qaq[j].xx] ^= 1;
            }
        }
        li += K;

    }
	return soln;
}

컴파일 시 표준 에러 (stderr) 메시지

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0 ; i < T.size(); i ++ ){
      |                     ~~^~~~~~~~~~
collapse.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0 ; i < X.size(); i ++ ){
      |                     ~~^~~~~~~~~~
collapse.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0 ; i < T.size(); i ++ ){
      |                     ~~^~~~~~~~~~
collapse.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0 ; i < W.size(); i ++ ){
      |                     ~~^~~~~~~~~~
collapse.cpp:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     while(li < qaq.size()){
      |           ~~~^~~~~~~~~~~~
collapse.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             while(pp < res.size() && res[pp].fi <= x.fi){
      |                   ~~~^~~~~~~~~~~~
collapse.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |             while(pp < res.size() && res[pp].fi > x.fi){
      |                   ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35