Submission #1222194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222194		steveonalex	Flood (IOI07_flood)	C++20	100 / 100	470 ms	27288 KiB

flood

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int INF = 1e9 + 69;

struct DSU{
    int n;
    vector<int> parent;

    DSU(int _n){
        n = _n;
        parent.resize(n, -1);
    }

    int find_set(int u){
        return (parent[u] < 0) ? u : (parent[u] = find_set(parent[u]));
    }
    bool same_set(int u, int v){return find_set(u) == find_set(v);}

    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (abs(parent[u]) < abs(parent[v])) swap(u, v);
            parent[u] += parent[v];
            parent[v] = u;
            return true;
        }
        return false;
    }
};

ostream& operator << (ostream &os, pair<int,int> x){
    return os << "(" << x.first << ", " << x.second << ")";
}

struct P{
    int x, y, z;
    P(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z){

    }
};

ll transform(P cur){
    ll ans = 0;
    ans += 1LL * cur.x * MASK(40) + 1LL * cur.y * MASK(20) + abs(cur.z);
    if (cur.z < 0) ans *= -1;
    return ans;
}

P transform_back(ll x){
    int sign = (x > 0); x = abs(x);
    P ans;
    ans.x = x >> 40;
    ans.y = (x >> 20) & (MASK(20) - 1);
    ans.z = x & (MASK(20) - 1);
    if (sign == false) ans.z *= -1;
    return ans;
}

vector<int> X, Y;
vector<ll> queriesX, queriesY;

void produce_point(vector<pair<int, int>> &pointsX){
    int init_sz = pointsX.size();

    multiset<int> S;
    int p = 0;
    int _p = 0;
    for(int i = 0; i < (int) X.size(); ++i){
        while(_p < (int) queriesX.size()){
            P cur = transform_back(queriesX[_p]);
            if (cur.x > i) break;
            if (cur.z < 0) {
                S.erase(S.find(cur.y));
            }
            else S.insert(cur.y);

            _p++;
        }
        while(p < init_sz){
            if (pointsX[p].first > i) break;
            int j = pointsX[p].second;

            auto it = S.upper_bound(j);
            if (it != S.end()){
                pointsX.push_back(make_pair(i, (*it) - 1));
            }
            p++;
        }
    }

    remove_dup(pointsX);
}

void solve(){
    int n; cin >> n;
    vector<pair<int, int>> pointsX;
    vector<pair<int, int>> a(n);
    for(int i= 0; i < n; ++i){
        int x, y; cin >> x>> y;
        a[i] = {x, y};
        for(int u = -1; u <= 0; ++u) for(int v = -1; v <= 0; ++v){
            pointsX.push_back(make_pair(x + u, y + v));
        }
    }

    for(pair<int, int> i: pointsX){
        X.push_back(i.first); Y.push_back(i.second);
    }
    remove_dup(X); remove_dup(Y);
    remove_dup(pointsX);
    for(auto &i: pointsX) {
        i.first = lower_bound(ALL(X), i.first) - X.begin();
        i.second = lower_bound(ALL(Y), i.second) - Y.begin();
    }
    for(auto &i: a){
        i.first = lower_bound(ALL(X), i.first) - X.begin();
        i.second = lower_bound(ALL(Y), i.second) - Y.begin();
    }

    int m; cin >> m;
    queriesX.reserve(m*2);
    queriesY.reserve(m*2);
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        u--; v--;
        pair<int,int> p1 = a[u], p2 = a[v];

        if (p1 > p2) swap(p1, p2);
        if (p1.first == p2.first){ // vertical
            int l = p1.second;
            int r = p2.second;
            queriesY.push_back(transform(P(l, p1.first, i)));
            queriesY.push_back(transform(P(r, p1.first, -i)));
        }
        else if (p1.second == p2.second){ // horizontal
            int l = p1.first;
            int r = p2.first;
            queriesX.push_back(transform(P(l, p1.second, i)));
            queriesX.push_back(transform(P(r, p1.second, -i)));
        }
    }

    sort(ALL(queriesX), [](ll a, ll b){return transform_back(a).x < transform_back(b).x;});
    sort(ALL(queriesY), [](ll a, ll b){return transform_back(a).x < transform_back(b).x;});

    produce_point(pointsX);

    vector<pair<int, int>> pointsY = pointsX;
    sort(ALL(pointsY), [](pair<int, int> x, pair<int, int> y){
        swap(x.first, x.second); swap(y.first, y.second);
        return x < y;
    }); 

    int ps = pointsX.size();

    set<pair<int, int>> S;
    DSU mst(ps+1);
    vector<pair<int, int>> edge(m+1);

    int _p = 0, p = 0;
    for(int i = 0; i < (int) X.size(); ++i){
        while(_p < (int) queriesX.size()){
            P cur = transform_back(queriesX[_p]);
            if (cur.x > i) break;
            if (cur.z < 0) {
                S.erase(make_pair(cur.y, -cur.z));
            }
            else S.insert(make_pair(cur.y, cur.z));

            _p++;
        }

        int l = p, r = p;   
        while(r < (int) pointsX.size()) {
            if (pointsX[r].first != i) break;
            ++r;
        }
        p = r;
        r--;

        if (l > r) continue;

        for(int j = l; j + 1 <= r; ++j){
            pair<int, int> p1 = pointsX[j], p2 = pointsX[j+1];
            int idx1 = j, idx2 = j + 1;
            pair<int, int> cur = make_pair(p1.second+1, -1);
            auto it = S.lower_bound(cur);

            int w = 0;
            if (it != S.end() && (*it).first <= p2.second) {
                w = (*it).second;
                it++;
                if (it != S.end() && (*it).first <= p2.second) {
                    w = -1;
                }
            }

            if (w >= 0){
                if (w == 0) {
                    mst.join_set(idx1, idx2);
                }
                else{
                    edge[w] = make_pair(idx1, idx2);
                }
            }
        }
        if (S.empty() || (*S.begin()).first > pointsX[l].second){
            int idx1 = l;
            mst.join_set(ps, idx1);

        }

        if (S.empty() || (*S.rbegin()).first <= pointsX[r].second){
            int idx2 = r;
            mst.join_set(ps, idx2);
        }
    }

    _p = 0, p = 0;
    for(int i = 0; i < (int) Y.size(); ++i){
        while(_p < (int) queriesY.size()){
            P cur = transform_back(queriesY[_p]);
            if (cur.x > i) break;
            if (cur.z < 0) {
                S.erase(make_pair(cur.y, -cur.z));
            }
            else S.insert(make_pair(cur.y, cur.z));

            _p++;
        }


        int l = p, r = p;   
        while(r < (int) pointsY.size()) {
            if (pointsY[r].second != i) break;
            ++r;
        }
        p = r;
        r--;

        if (l > r) continue;


        for(int j = l; j + 1 <= r; ++j){
            pair<int, int> p1 = pointsY[j], p2 = pointsY[j+1];
            int idx1 = lower_bound(ALL(pointsX), p1) - pointsX.begin();
            int idx2 = lower_bound(ALL(pointsX), p2) - pointsX.begin();
            pair<int, int> cur = make_pair(pointsY[j].first+1, -1);
            auto it = S.lower_bound(cur);

            int w = 0;
            if (it != S.end() && (*it).first <= pointsY[j+1].first) {
                w = (*it).second;
                it++;
                if (it != S.end() && (*it).first <= pointsY[j+1].first) {
                    w = -1;
                }
            }

            if (w >= 0){
                if (w == 0){
                    mst.join_set(idx1, idx2);
                }
                else{
                    edge[w] = make_pair(idx1, idx2);
                }
            }
        }

        if (S.empty() || (*S.begin()).first > pointsY[l].first){
            pair<int, int> p1 = pointsY[l];
            int idx1 = lower_bound(ALL(pointsX), p1) - pointsX.begin();
            mst.join_set(ps, idx1);
        }

        if (S.empty() || (*S.rbegin()).first <= pointsY[r].first){
            pair<int, int> p2 = pointsY[r];
            int idx2 = lower_bound(ALL(pointsX), p2) - pointsX.begin();
            mst.join_set(ps, idx2);
        }
    }

    vector<int> L(ps+1), R(ps+1);

    for(pair<int, int> &i: edge) {
        i.first = mst.find_set(i.first);
        i.second = mst.find_set(i.second);
        R[i.first]++;
        R[i.second]++;
    }
    for(int i = 1; i <= ps; ++i) {
        R[i] += R[i-1];
        L[i] = R[i-1];
    }
    vector<int> edging(R.back());
    for(int i= 0; i <= ps; ++i) R[i] = L[i];
    for(int i = 1; i <= m; ++i){
        int u, v; tie(u, v) = edge[i];
        edging[R[u]++] = i;
        edging[R[v]++] = i;
    }

    int source = mst.find_set(ps);
    vector<int> dis(ps+1, INF); dis[source] = 0;
    deque<int> q; q.push_back(source);
    while(q.size()){
        int u = q.front(); q.pop_front();
        for(int j = L[u]; j < R[u]; ++j) {
            int v = edging[j];
            int nxt = edge[v].first ^ edge[v].second ^ u;
            if (minimize(dis[nxt], dis[u] + 1))
                q.push_back(nxt);
        }
    }

    vector<int> ans;
    for(int i = 1; i <= m; ++i){
        int u, v; tie(u, v) = edge[i];
        if (dis[u] == dis[v]) ans.push_back(i); 
    }
    cout << ans.size() << "\n";
    printArr(ans, "\n", "");

}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
    clock_t start = clock();

    // freopen("input.inp", "r", stdin);

    solve();

    cerr << "Time elapsed: " << clock() - start << "ms!\n";
 
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9