oj.uz

Submission #211948

# Submission time Handle Problem Language Result Execution time Memory
211948 2020-03-21T19:47:13 Z tatyam Flood (IOI07_flood) C++17
81 / 100
 2000 ms 8556 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)


struct wall{
    int to = -1, index;
    wall(){}
    wall(int to, int index): to(to), index(index){}
    bool exist() const { return to + 1; }
};
struct Eraseable_Heap{
    priority_queue<tuplis, vector<tuplis>, greater<tuplis>> q, e;
    void push(const tuplis& a){ q.push(a); }
    tuplis top() const { return q.top(); }
    void erase(const tuplis& a){
        if(q.top() == a){
            q.pop();
            while(e.size() && q.top() == e.top()){
                q.pop();
                e.pop();
            }
        }
        else e.push(a);
    }
    bool empty() const { return q.empty(); }
};
int main(){
    int n;
    scanf("%d", &n);
    vector<pii> p(n);
    each(i, p) scanf("%d%d", &i.first, &i.second);
    Eraseable_Heap min_p;
    rep(n) min_p.push({p[i].first, p[i].second, i});
    vector<array<wall, 4>> g(n);
    auto submerge = [&](int i) -> void {
        if(!any_of(all(g[i]), [](const wall& w){ return w.exist(); })) min_p.erase({p[i].first, p[i].second, i});
    };
    int w;
    scanf("%d", &w);
    rep(w){
        int a, b;
        scanf("%d%d", &a, &b);
        a--; b--;
        int d = 0;
        if(p[a].first < p[b].first) d = 0;
        else if(p[a].first > p[b].first) d = 2;
        else if(p[a].second < p[b].second) d = 1;
        else d = 3;
        g[a][d] = {b, i};
        g[b][d ^ 2] = {a, i};
    }
    vector<bool> ans(w, 1);
    while(!min_p.empty()){
        int start = min_p.top()[2], at = start, d = 0;
        vector<pii> visit;
        if(!g[at][d].exist()) d = 1;
        do{
            if(!g[at][d].exist()){
                d++;
                d &= 3;
                continue;
            }
            visit.emplace_back(at, d);
            ans[g[at][d].index] = !ans[g[at][d].index];
            at = g[at][d].to;
            d--;
            d &= 3;
        }while(at != start);
        each(i, visit){
            int at, d;
            tie(at, d) = i;
            if(!g[at][d].exist()) continue;
            int at2 = g[at][d].to, d2 = d ^ 2;
            g[at][d].to = -1;
            g[at2][d2].to = -1;
            submerge(at);
            submerge(at2);
        }
    }
    printf("%d\n", accumulate(ans.begin(), ans.end(), 0));
    rep(w) if(ans[i]) printf("%d\n", i + 1);
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
flood.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     each(i, p) scanf("%d%d", &i.first, &i.second);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &w);
     ~~~~~^~~~~~~~~~
flood.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2109 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 256 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 1916 KB Time limit exceeded

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5996 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 6316 KB Output is correct
2 Correct 167 ms 6360 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 6508 KB Output is correct
2 Correct 146 ms 6380 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 7148 KB Output is correct
2 Correct 100 ms 8556 KB Output is correct