| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 868355 |
2023-10-31T07:55:05 Z |
josanneo22 |
Flood (IOI07_flood) |
C++17 |
|
2000 ms |
32364 KB |
#pragma warning(disable : 4996)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(), x.end()
#define orz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
char buf[1 << 23], * p1 = buf, * p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
int s = 0;
char ch = getchar(), last;
while (ch < '0' || ch>'9') last = ch, ch = getchar();
while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return last == '-' ? -s : s;
}
int num[100];
inline void rt(int x)
{
if (x < 0) putchar('-'), x = -x;;
int len = 0;
do num[len++] = x % 10; while (x /= 10);
while (len--) putchar(num[len] + '0');
}
const int N = 1e5 + 50;
int n, x[N], y[N], to[N][4], dr[N][4], m;
inline int orientation(int a, int b) {
if (y[a] == y[b]) return x[a] > x[b];
return 2 + (y[a] > y[b]);
}
int head[N << 2], cnt = 0;
struct edge {
int to, next, val;
}edge[N<<2];
inline void add_edge(int u, int v, int w) {
edge[cnt].next = head[u], edge[cnt].to = v, edge[cnt].val = w, head[u] = cnt++;
edge[cnt].next = head[v], edge[cnt].to = u, edge[cnt].val = w, head[v] = cnt++;
}
signed main() {
orz;
n = rd();
L(i, 1, n) x[i] = rd(), y[i] = rd();
m = rd();
L(i, 1, m) {
int u = rd(), v = rd();
dr[u][orientation(u, v)] = dr[v][orientation(v, u)] = i;
to[u][orientation(u, v)] = v; to[v][orientation(v, u)] = u;
add_edge(i, i + m, 1);
}
L(i, 1, n) {
vector<int> p;
if (dr[i][0])p.push_back(0);
if (dr[i][2])p.push_back(2);
if (dr[i][1])p.push_back(1);
if (dr[i][3])p.push_back(3);
if (p.size() == 0) continue;
for (int j = 0; j + 1 < p.size(); j++) {
int u = p[j], v = p[j + 1];
add_edge(dr[i][u] + (u == 1 || u == 2) * m, dr[i][v] + (v == 0 || v == 3) * m, 0);
}
int u = p.back(), v = p.front();
add_edge(dr[i][u] + (u == 1 || u == 2) * m, dr[i][v] + (v == 0 || v == 3) * m, 0);
}
vector<int> vis(N*4), dis(N*4, 1E9);
int S = 0, mxy = -1;
function<void(int)> dye = [&](int u) {
vis[u] = true;
L(i, 0, 3) {
if (dr[u][i]==0)continue;
if ((i == 0 || i == 2) && y[u] > mxy) {
mxy = y[u]; S = dr[u][i];
}
if (!vis[to[u][i]]) dye(to[u][i]);
}
};
function<void()> bfs = [&]() {
deque<int>q;
q.push_back(S), dis[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int i = head[u]; i != -1; i = edge[i].next) {
if (dis[edge[i].to] <= dis[u] + edge[i].val) continue;
dis[edge[i].to] = dis[u] + edge[i].val;
if (edge[i].val)q.push_back(edge[i].to);
else q.push_front(edge[i].to);
}
}
};
L(i, 1, n) {
if (vis[i]) continue;
S = 0; mxy = -1; dye(i);
if (S) bfs();
}
int ans = 0;
L(i, 1, m) ans += (dis[i] != 1E9 && dis[i] == dis[i + m]);
printf("%d\n", ans);
L(i, 1, m) if (dis[i] == dis[i + m]) printf("%d\n", i);
}
Compilation message
flood.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
1 | #pragma warning(disable : 4996)
|
flood.cpp: In function 'int main()':
flood.cpp:63:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int j = 0; j + 1 < p.size(); j++) {
| ~~~~~~^~~~~~~~~~
flood.cpp: In function 'int rd()':
flood.cpp:20:24: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
20 | return last == '-' ? -s : s;
| ~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2053 ms |
9564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
9816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
9560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2021 ms |
9560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2019 ms |
9560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
9560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2044 ms |
9564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2044 ms |
9564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
9560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
13916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2043 ms |
17448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
15960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
32092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
32364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
