| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 349963 |
2021-01-18T18:57:01 Z |
negar_a |
Flood (IOI07_flood) |
C++14 |
|
69 ms |
19820 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int maxn = 2e5 + 10;
int x[maxn], y[maxn], a[maxn], b[maxn];
int dis[maxn], ty[maxn][5];
vector <pii> adj[maxn];
int inf = 1e8;
int dir(int u, int v){
// left = 0, down = 1, right = 2, up = 3;
if(x[u] == x[v]){
if(y[u] < y[v]){
return 3;
}
return 1;
}
if(x[u] < x[v])
return 2;
return 0;
}
void add_edge(int x, int y){
adj[x].pb({y, 0});
adj[y].pb({x, 0});
return;
}
void bfs(int v){
deque <int> q;
dis[v] = 0;
q.pb(v);
while(q.size()){
int x = q.front();
q.pop_front();
for(auto u : adj[x]){
if(dis[u.F] > dis[x] + u.S){
dis[u.F] = dis[x] + u.S;
if(u.S){
q.pb(u.F);
}else
q.push_front(u.F);
}
}
}
}
int main(){
fast_io;
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> x[i] >> y[i];
}
int m;
cin >> m;
//find lines for each point
for(int i = 1; i <= m; i ++)
ty[i][0] = ty[i][1] = ty[i][2] = ty[i][3] = -1;
for(int i = 1; i <= m; i ++){
cin >> a[i] >> b[i];
ty[a[i]][dir(a[i], b[i])] = i;
ty[b[i]][dir(b[i], a[i])] = i;
}
//put edges of the graph!
for(int i = 1; i <= n; i ++){
for(int j = 0; j < 4; j ++){
if(ty[i][j]){
int k = (j + 1) % 4;
while(ty[i][k] == -1){
k = (k + 1) % 4;
}
int x = 2 * ty[i][j] + ((j == 0) || (j == 3));
int y = 2 * ty[i][k] + ((k == 1) || (k == 2));
adj[ty[i][j] * 2].pb({ty[i][j] * 2 + 1, 1});
adj[ty[i][k] * 2].pb({ty[i][k] * 2 + 1, 1});
adj[ty[i][j] * 2 + 1].pb({ty[i][j] * 2, 1});
adj[ty[i][k] * 2 + 1].pb({ty[i][k] * 2, 1});
add_edge(x, y);
}
}
}
for(int i = 0; i <= 2 * m + 3; i ++)
dis[i] = inf;
vector <pii> v;
for(int i = 1; i <= m; i ++){
if(x[a[i]] == x[b[i]])
v.pb({min(y[a[i]], y[b[i]]), i});
}
sort(v.begin(), v.end());
for(auto u : v){
if(dis[2 * u.S + 1] >= inf){
bfs(2 * u.S + 1);
}
}
int cnt = 0;
for(int i = 1; i <= m; i ++){
if(dis[2 * i] == dis[2 * i + 1])
cnt ++;
}
cout << cnt << '\n';
for(int i = 1; i <= m; i ++){
if(dis[2 * i] == dis[2 * i + 1])
cout << i << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
11756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
15980 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
16492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
18412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
19820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
