oj.uz

답안 #410288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410288 2021-05-22T12:24:08 Z doowey Collapse (JOI18_collapse) C++14
5 / 100
 4700 ms 9144 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 = 10010;
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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 844 KB Output is correct
2 Correct 63 ms 588 KB Output is correct
3 Correct 58 ms 588 KB Output is correct
4 Correct 58 ms 552 KB Output is correct
5 Correct 377 ms 908 KB Output is correct
6 Correct 679 ms 908 KB Output is correct
7 Correct 51 ms 664 KB Output is correct
8 Correct 57 ms 708 KB Output is correct
9 Correct 428 ms 924 KB Output is correct
10 Correct 547 ms 908 KB Output is correct
11 Correct 883 ms 1040 KB Output is correct
12 Correct 854 ms 1036 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1989 ms 4032 KB Output is correct
2 Correct 2024 ms 4032 KB Output is correct
3 Correct 3813 ms 9144 KB Output is correct
4 Correct 1979 ms 4024 KB Output is correct
5 Correct 4700 ms 9144 KB Output is correct
6 Incorrect 3443 ms 5160 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1987 ms 4032 KB Output is correct
2 Correct 1983 ms 4024 KB Output is correct
3 Incorrect 2023 ms 4048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 844 KB Output is correct
2 Correct 63 ms 588 KB Output is correct
3 Correct 58 ms 588 KB Output is correct
4 Correct 58 ms 552 KB Output is correct
5 Correct 377 ms 908 KB Output is correct
6 Correct 679 ms 908 KB Output is correct
7 Correct 51 ms 664 KB Output is correct
8 Correct 57 ms 708 KB Output is correct
9 Correct 428 ms 924 KB Output is correct
10 Correct 547 ms 908 KB Output is correct
11 Correct 883 ms 1040 KB Output is correct
12 Correct 854 ms 1036 KB Output is correct
13 Correct 1989 ms 4032 KB Output is correct
14 Correct 2024 ms 4032 KB Output is correct
15 Correct 3813 ms 9144 KB Output is correct
16 Correct 1979 ms 4024 KB Output is correct
17 Correct 4700 ms 9144 KB Output is correct
18 Incorrect 3443 ms 5160 KB Output isn't correct
19 Halted 0 ms 0 KB -