Submission #1221926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221926		steveonalex	Flood (IOI07_flood)	C++20	64 / 100	812 ms	98980 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;

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

vector<pair<int, int>> produce_point(vector<pair<int, int>> points, vector<int> X, vector<int> Y, 
    vector<vector<pair<int, int>>> queriesX, vector<vector<pair<int, int>>> queriesY){
    vector<vector<int>> coordX(X.size()), coordY(Y.size());
    for(pair<int, int> i: points){
        int x = lower_bound(ALL(X), i.first) - X.begin();
        int y = lower_bound(ALL(Y), i.second) - Y.begin();
        coordX[x].push_back(i.second);
        coordY[y].push_back(i.first);
    }
    for(int i = 0; i < (int) X.size(); ++i)
        remove_dup(coordX[i]);
    for(int i = 0; i < (int) Y.size(); ++i) 
        remove_dup(coordY[i]);

    vector<pair<int, int>> ans = points;

    multiset<int> S;

    for(int i = 0; i < (int) X.size(); ++i){
        for(pair<int, int> j: queriesX[i]){
            if (j.second < 0){
                S.erase(S.find(j.first));
            }
            else{
                S.insert(j.first);
            }
        }
        for(int j: coordX[i]){
            auto it = S.upper_bound(j);
            vector<int> arr;
            arr.push_back(j);
            if (it != S.end()){
                arr.push_back((*it) - 1);
                ans.push_back(make_pair(X[i], (*it) - 1));
            }
            if (it != S.begin()){
                it--;
                arr.push_back((*it));
                ans.push_back(make_pair(X[i], (*it)));
            }
            remove_dup(arr);
        }
    }
    for(int i = 0; i < (int) Y.size(); ++i){
        for(pair<int, int> j: queriesY[i]){
            if (j.second < 0){
                S.erase(S.find(j.first));
            }
            else{
                S.insert(j.first);
            }
        }

        for(int j: coordY[i]){
            auto it = S.lower_bound(j+1);
            if (it != S.end()){
                ans.push_back(make_pair((*it) - 1, Y[i]));
            }
            if (it != S.begin()){
                it--;
                ans.push_back(make_pair((*it), Y[i]));
            }
        }
    }

    remove_dup(ans);
    return ans;
}

void solve(){
    int n; cin >> n;
    vector<pair<int, int>> points;
    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){
            points.push_back(make_pair(x + u, y + v));
        }
    }

    vector<int> X, Y;
    for(pair<int, int> i: points){
        X.push_back(i.first); Y.push_back(i.second);
    }
    remove_dup(X); remove_dup(Y);
    remove_dup(points);

    vector<vector<pair<int, int>>> queriesX(X.size()), queriesY(Y.size());

    int m; cin >> m;

    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 = lower_bound(ALL(Y), p1.second) - Y.begin();
            int r = lower_bound(ALL(Y), p2.second) - Y.begin();
            queriesY[l].push_back(make_pair(p1.first, i));
            queriesY[r].push_back(make_pair(p1.first, -i));
        }
        else if (p1.second == p2.second){ // horizontal
            int l = lower_bound(ALL(X), p1.first) - X.begin();
            int r = lower_bound(ALL(X), p2.first) - X.begin();
            queriesX[l].push_back(make_pair(p1.second, i));
            queriesX[r].push_back(make_pair(p1.second, -i));
        }
    }

    points = produce_point(points, X, Y, queriesX, queriesY);

    vector<vector<int>> coordX(X.size()), coordY(Y.size());
    for(pair<int, int> i: points){
        int x = lower_bound(ALL(X), i.first) - X.begin();
        int y = lower_bound(ALL(Y), i.second) - Y.begin();
        coordX[x].push_back(i.second);
        coordY[y].push_back(i.first);
    }
    for(int i = 0; i < (int) X.size(); ++i)
        remove_dup(coordX[i]);
    for(int i = 0; i < (int) Y.size(); ++i) 
        remove_dup(coordY[i]);

    int ps = points.size();
    vector<vector<pair<int, int>>> graph(ps+1);

    set<pair<int, int>> S;

    for(int i = 0; i < (int) X.size(); ++i){
        for(pair<int, int> j: queriesX[i]){
            if (j.second < 0){
                S.erase(make_pair(j.first, -j.second));
            }
            else{
                S.insert(make_pair(j.first, j.second));
            }
        }

        for(int j = 0; j + 1 < (int) coordX[i].size(); ++j){
            pair<int, int> p1 = make_pair(X[i], coordX[i][j]), p2 = make_pair(X[i], coordX[i][j+1]);
            int idx1 = lower_bound(ALL(points), p1) - points.begin();
            int idx2 = lower_bound(ALL(points), p2) - points.begin();
            pair<int, int> cur = make_pair(coordX[i][j]+1, -1);
            auto it = S.lower_bound(cur);

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

            if (w >= 0){
                graph[idx1].push_back(make_pair(idx2, w));
                graph[idx2].push_back(make_pair(idx1, w));
            }
        }
        if (S.empty() || (*S.begin()).first > coordX[i][0]){
            pair<int, int> p1 = make_pair(X[i], coordX[i][0]);
            int idx1 = lower_bound(ALL(points), p1) - points.begin();
            graph[idx1].push_back(make_pair(ps, 0));
            graph[ps].push_back(make_pair(idx1, 0));

        }

        if (S.empty() || (*S.rbegin()).first <= coordX[i].back()){
            pair<int, int> p2 = make_pair(X[i], coordX[i].back());
            int idx2 = lower_bound(ALL(points), p2) - points.begin();
            graph[idx2].push_back(make_pair(ps, 0));
            graph[ps].push_back(make_pair(idx2, 0));
        }
    }

    for(int i = 0; i < (int) Y.size(); ++i){
        for(pair<int, int> j: queriesY[i]){
            if (j.second < 0){
                S.erase(make_pair(j.first, -j.second));
            }
            else{
                S.insert(make_pair(j.first, j.second));
            }
        }

        for(int j = 0; j + 1 < (int) coordY[i].size(); ++j){
            pair<int, int> p1 = make_pair(coordY[i][j], Y[i]), p2 = make_pair(coordY[i][j+1], Y[i]);
            int idx1 = lower_bound(ALL(points), p1) - points.begin();
            int idx2 = lower_bound(ALL(points), p2) - points.begin();
            pair<int, int> cur = make_pair(coordY[i][j]+1, -1);
            auto it = S.lower_bound(cur);

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

            if (w >= 0){
                graph[idx1].push_back(make_pair(idx2, w));
                graph[idx2].push_back(make_pair(idx1, w));
            }
        }

        if (S.empty() || (*S.begin()).first > coordY[i][0]){
            pair<int, int> p1 = make_pair(coordY[i][0], Y[i]);
            int idx1 = lower_bound(ALL(points), p1) - points.begin();
            graph[idx1].push_back(make_pair(ps, 0));
            graph[ps].push_back(make_pair(idx1, 0));
        }

        if (S.empty() || (*S.rbegin()).first <= coordY[i].back()){
            pair<int, int> p2 = make_pair(coordY[i].back(), Y[i]);
            int idx2 = lower_bound(ALL(points), p2) - points.begin();
            graph[idx2].push_back(make_pair(ps, 0));
            graph[ps].push_back(make_pair(idx2, 0));
        }
    }

    vector<int> dis(ps+1, INF); dis[ps] = 0;
    deque<int> q; q.push_back(ps);
    while(q.size()){
        int u = q.front(); q.pop_front();
        for(pair<int, int> v: graph[u]) {
            if (v.second){
                if (minimize(dis[v.first], dis[u] + 1))
                    q.push_back(v.first);
            }
            else{
                if (minimize(dis[v.first], dis[u]))
                    q.push_front(v.first);
            }
        }
    }

    vector<int> check(m+1, 1);
    for(int i = 0; i <= ps; ++i){
        for(pair<int, int> j: graph[i]) if (j.second){
            if (dis[j.first] == dis[i] + 1)
                check[j.second] = 0;
        }
    }

    vector<int> ans;
    for(int i = 1; i <= m; ++i) if (check[i]) ans.push_back(i);
    cout << ans.size() << "\n";
    printArr(ans);

}

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: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9