oj.uz

답안 #410287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410287 2021-05-22T12:23:02 Z doowey Collapse (JOI18_collapse) C++14
0 / 100
 2534 ms 10936 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 844 KB Output is correct
2 Correct 53 ms 624 KB Output is correct
3 Correct 62 ms 588 KB Output is correct
4 Correct 58 ms 588 KB Output is correct
5 Correct 167 ms 972 KB Output is correct
6 Correct 315 ms 972 KB Output is correct
7 Correct 57 ms 708 KB Output is correct
8 Correct 54 ms 688 KB Output is correct
9 Correct 190 ms 1036 KB Output is correct
10 Incorrect 279 ms 1036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 4012 KB Output is correct
2 Correct 1024 ms 4024 KB Output is correct
3 Correct 1955 ms 9140 KB Output is correct
4 Correct 1006 ms 4416 KB Output is correct
5 Incorrect 2534 ms 10936 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 998 ms 3920 KB Output is correct
2 Correct 1008 ms 4024 KB Output is correct
3 Correct 1006 ms 4032 KB Output is correct
4 Correct 1010 ms 4032 KB Output is correct
5 Incorrect 1110 ms 4032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 844 KB Output is correct
2 Correct 53 ms 624 KB Output is correct
3 Correct 62 ms 588 KB Output is correct
4 Correct 58 ms 588 KB Output is correct
5 Correct 167 ms 972 KB Output is correct
6 Correct 315 ms 972 KB Output is correct
7 Correct 57 ms 708 KB Output is correct
8 Correct 54 ms 688 KB Output is correct
9 Correct 190 ms 1036 KB Output is correct
10 Incorrect 279 ms 1036 KB Output isn't correct
11 Halted 0 ms 0 KB -