| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 349935 |
2021-01-18T17:59:51 Z |
Sara |
Flood (IOI07_flood) |
C++14 |
|
436 ms |
45920 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 = 1e5 + 10;
int x[maxn], y[maxn], a[2 * maxn], b[2 * maxn];
int dis[4 * maxn];
vector <pii> vec[maxn];
vector <pii> adj[4 * maxn];
bool mark[4 * 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 d1, int d2, int a, int b){
// cout << a << " " << b << " | " << d1 << " " << d2 << endl;
// if two lines are : |_
if(d1 == 0 && d2 == 1){
adj[2 * a + 1].pb({2 * b + 1, 0});
adj[2 * b + 1].pb({2 * a + 1, 0});
}
else if(d1 == 1 && d2 == 2){
adj[2 * a].pb({2 * b + 1, 0});
adj[2 * b + 1].pb({2 * a, 0});
}
else if(d1 == 2 && d2 == 3){
adj[2 * a].pb({2 * b, 0});
adj[2 * b].pb({2 * a, 0});
}
else if(d1 == 3 && d2 == 0){
adj[2 * a + 1].pb({2 * b, 0});
adj[2 * b].pb({2 * a + 1, 0});
}
// if they are _ _
else if((d1 == 3 && d2 == 1) || (d1 == 0 && d2 == 2)){
adj[2 * a + 1].pb({2 * b + 1, 0});
adj[2 * b + 1].pb({2 * a + 1, 0});
}
else if((d1 == 1 && d2 == 3) || (d1 == 2 && d2 == 0)){
adj[2 * a].pb({2 * b, 0});
adj[2 * b].pb({2 * a, 0});
}
//
else if(d1 == 0 && d2 == 3){
adj[2 * a + 1].pb({2 * b, 0});
adj[2 * b].pb({2 * a + 1, 0});
}
else if(d1 == 1 && d2 == 0){
adj[2 * a].pb({2 * b, 0});
adj[2 * b].pb({2 * a, 0});
}
else if(d1 == 2 && d2 == 1){
adj[2 * a].pb({2 * b + 1, 0});
adj[2 * b + 1].pb({2 * a, 0});
}
else if(d1 == 3 && d2 == 2){
adj[2 * a + 1].pb({2 * b + 1, 0});
adj[2 * b + 1].pb({2 * a + 1, 0});
}
//alone:(
else{
adj[2 * a].pb({2 * a + 1, 0});
}
adj[2 * a].pb({2 * a + 1, 1});
adj[2 * a + 1].pb({2 * a, 1});
adj[2 * b].pb({2 * b + 1, 1});
adj[2 * b + 1].pb({2 * b, 1});
return;
}
void bfs(int v){
deque <int> q;
dis[v] = 0;
q.pb(v);
while(q.size()){
int x = q.front();
mark[x] = true;
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 ++){
cin >> a[i] >> b[i];
vec[a[i]].pb({dir(a[i], b[i]), i});
vec[b[i]].pb({dir(b[i], a[i]), i});
}
//put edges of the graph!
for(int i = 1; i <= n; i ++){
sort(vec[i].begin(), vec[i].end());
for(int j = 0; j < (int)vec[i].size() - 1; j ++){
add_edge(vec[i][j].F, vec[i][j + 1].F, vec[i][j].S, vec[i][j + 1].S);
}
if((int)vec[i].size() > 1)
add_edge(vec[i].back().F, vec[i][0].F, vec[i].back().S, vec[i][0].S);
else if((int)vec[i].size() == 1){
add_edge(-1, -1, vec[i][0].S, -1);
}
}
fill(dis, dis + 4 * maxn, 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(!mark[2 * u.S + 1]){
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 << endl;
for(int i = 1; i <= m; i ++){
if(dis[2 * i] == dis[2 * i + 1])
cout << i << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
13676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13676 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13676 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13804 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
13952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
13804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
18412 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
161 ms |
31084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
32624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
430 ms |
41320 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
436 ms |
45920 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
