oj.uz

Submission #240739

# Submission time Handle Problem Language Result Execution time Memory
240739 2020-06-21T04:10:57 Z thecodingwizard Flood (IOI07_flood) C++11
73 / 100
 665 ms 44400 KB 
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define ll long long

ii A[100000];
struct Wall {
    int a, b;
    int idx;

    bool operator<(const Wall &other) const {
        int x = min(A[a].f, A[b].f);
        int y = min(A[other.a].f, A[other.b].f);
        int X = max(A[a].f, A[b].f);
        int Y = max(A[other.a].f, A[other.b].f);
        if (x==y&&X==Y) {
            return idx < other.idx;
        }
        return x==y?X<Y:x<y;
    }
};

int n;
vector<int> graph[100000];
vector<Wall> walls;
set<Wall> sortedWalls;
bool vis[200000][2];
bool done[200000];
vector<int> justDone;

ll cross(int a, int b, int c) {
    int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
    int cross = (ll)w*z-(ll)x*y;
    return cross;
}

bool turnRight(int a, int b, int c) {
    return cross(a, b, c) < 0;
}
bool turnLeft(int a, int b, int c) {
    return cross(a, b, c) > 0;
}
bool goForward(int a, int b, int c) {
    int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
    //return (w==y&&(x<0)==(z<0))||(x==z&&(w<0)==(y<0));
    return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
}

bool goBack(int a, int b, int c) {
    int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
    return (w==y&&(x<0)!=(z<0))||(x==z&&(w<0)!=(y<0));
    return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
}

void go(int u, int dir) {
    //cout << "go: " << u << " " << dir << endl;
    if (vis[u][dir]) return;
    vis[u][dir] = true;
    justDone.push_back(u);
    Wall w = walls[u];
    sortedWalls.erase(w);

    int prvNode = dir == 0 ? w.b : w.a;
    int node = dir == 0 ? w.a : w.b;

    // left
    for (int wID : graph[node]) {
        int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
        int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
        if (!done[wID] && turnLeft(prvNode, node, nxtNode)) {
            //cout << "left" << endl;
            return go(wID, nxtDir);
        }
    }

    // forward
    for (int wID : graph[node]) {
        int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
        int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
        if (!done[wID] && goForward(prvNode, node, nxtNode)) {
            //cout << "forward" << endl;
            return go(wID, nxtDir);
        }
    }
    
    // right
    for (int wID : graph[node]) {
        int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
        int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
        if (!done[wID] && turnRight(prvNode, node, nxtNode)) {
            //cout << "right" << endl;
            return go(wID, nxtDir);
        }
    }
    
    // back
    for (int wID : graph[node]) {
        int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
        int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
        if (!done[wID]) {
            assert(goBack(prvNode, node, nxtNode));
            //cout << "back" << endl;
            return go(wID, nxtDir);
        }
    }
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i].f >> A[i].s;
    int w; cin >> w;
    for (int i = 0; i < w; i++) {
        int a, b; cin >> a >> b; --a; --b;
        sortedWalls.insert({a,b,i});
        walls.push_back({a,b,i});
        graph[a].push_back(i);
        graph[b].push_back(i);
        vis[i][0] = vis[i][1] = false;
        done[i] = false;
    }

    while (!sortedWalls.empty()) {
        //cout << "=== new go ===" << endl;
        int u = sortedWalls.begin()->idx;
        int x = A[walls[u].a].f - A[walls[u].b].f, y = A[walls[u].b].s - A[walls[u].a].s;
        if (x<0||y<0) {
            go(sortedWalls.begin()->idx, 0);
        } else {
            go(sortedWalls.begin()->idx, 1);
        }
        
        for (int x : justDone) done[x] = true;
        justDone.clear();
    }

    vector<int> ans;
    for (int i = 0; i < w; i++) {
        if (vis[i][0] && vis[i][1]) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i]+1 << endl;
    }

    return 0;
}

Compilation message

flood.cpp: In function 'bool goForward(int, int, int)':
flood.cpp:50:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
                                                           ^
flood.cpp:50:155: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
                                                                                                                                                           ^
flood.cpp:48:9: warning: unused variable 'w' [-Wunused-variable]
     int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
         ^
flood.cpp:48:28: warning: unused variable 'x' [-Wunused-variable]
     int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
                            ^
flood.cpp:48:49: warning: unused variable 'y' [-Wunused-variable]
     int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
                                                 ^
flood.cpp:48:70: warning: unused variable 'z' [-Wunused-variable]
     int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
                                                                      ^
flood.cpp: In function 'bool goBack(int, int, int)':
flood.cpp:56:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
                                                           ^
flood.cpp:56:155: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
                                                                                                                                                           ^
flood.cpp: In function 'int main()':
flood.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); i++) {
                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 17832 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 26532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 600 ms 17836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 19352 KB Output is correct
2 Runtime error 639 ms 44400 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)