Submission #240739

#TimeUsernameProblemLanguageResultExecution timeMemory
240739thecodingwizardFlood (IOI07_flood)C++11
73 / 100
665 ms44400 KiB
#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 (stderr)

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++) {
                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...