| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129628 |
2019-07-12T19:49:19 Z |
khulegub |
Flood (IOI07_flood) |
C++14 |
|
330 ms |
65540 KB |
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long i64;
int xac = 0;
int n;
int w;
// bool dbg = 0;
bool vis[100005];
int to[100005][4];
bool path[100005];
int tocnt[100005];
vector<pii> p;
vector<pii> wll;
void mark(int u){
vis[u] = 1;
for (int i = 0; i < 4; i++){
if (to[u][i] != 0 and !vis[to[u][i]]){
mark( to[u][i] );
}
}
}
int dfs(int u, int dir){
if (path[u]) return u;
// cout << u << '&' << dir << '\n';
// if (dbg and u == 4) cout << dir;
path[u] = 1;
if (dir == -1){ //init
if (tocnt[u] != 2){
int daj;
queue <int> q;
bool vis2[100005];
memset(vis2, 0, sizeof vis2);
q.push(u);
vis2[u] = 1;
while (!q.empty()){
int nw = q.front();
q.pop();
if(tocnt[nw] == 2){
daj = nw;
break;
}
for (int i = 0; i < 4; i++){
int v = to[nw][i];
if(v != 0 and !vis2[v]){
q.push(v);
vis2[v] = 1;
}
}
}
path[u] = 0;
return dfs(daj, -1);
}
int arr[2] = {-1, -1};
for (int i = 0; i < 4; i++){
int v = to[u][i];
if (v != 0){
if (arr[0] == -1){
arr[0] = i;
}
else arr[1] = i;
}
}
if ((arr[0] + 1) % 4 == arr[1]) swap(arr[0], arr[1]);
for (int i = 0; i < 2; i++){
int v = to[u][arr[i]];
if (v != 0){
int tmp = dfs(v, arr[i]);
if (tmp != -1){
to[u][arr[i]] = 0;
to[v][ (arr[i] + 2) % 4 ] = 0;
tocnt[u]--;
tocnt[v]--;
xac++;
if (tmp != u){
path[u] = 0;
return tmp;
}
}
}
}
}
else{
int arr[3];
arr[0] = (dir + 1) % 4;
arr[1] = dir;
arr[2] = (dir + 3) % 4;
for (int i = 0; i < 3; i++){
int v = to[u][arr[i]];
if (v != 0){
int tmp = dfs(v, arr[i]);
if (tmp != -1){
to[u][arr[i]] = 0;
to[v][ (arr[i] + 2) % 4 ] = 0;
tocnt[u]--;
tocnt[v]--;
xac++;
if (tmp != u){
path[u] = 0;
return tmp;
}
}
}
}
}
path[u] = 0;
return -1;
}
int main(){
// freopen("in.txt", "r", stdin);
cin >> n;
p.resize(n + 1);
for (int i = 1, tx, ty; i <= n; i++){
cin >> tx >> ty;
p[i] = mp(tx, ty);
}
cin >> w;
wll.resize(w + 1);
// 0 top
// 1 baruun
// 2 bot
// 3 zuun
for (int i = 1, a, b; i <= w; i++){
cin >> a >> b;
int dx = p[b].xx - p[a].xx;
int dy = p[b].yy - p[a].yy;
int dir;
tocnt[a]++;
tocnt[b]++;
if (dx != 0){ // horizontal
if (dx > 0){ // a b
to[a][1] = b;
to[b][3] = a;
dir = 1;
}
else { // b a
to[a][3] = b;
to[b][1] = a;
dir = 3;
}
}
else{ //vert
if (dy > 0){ // b ni deer
to[a][0] = b;
to[b][2] = a;
dir = 0;
}
else{
to[a][2] = b;
to[b][0] = a;
dir = 2;
}
}
wll[i] = mp(a, dir);
}
for (int i = 1; i <= n; i++){
if (!vis[i]){
// if (i == 4) dbg = 1;
dfs(i, -1);
mark(i);
// if (i == 4) dbg = 0;
// cout << i << '&' << vis[11] << ' ';
// break;
}
}
// cout << "##################\n";
cout << w - xac << '\n';
for (int i = 1; i <= w; i++){
if ( to[wll[i].xx][wll[i].yy] != 0 ) cout << i << '\n';
// if ( to[wll[i].xx][wll[i].yy] != 0 ) cout << wll[i].xx << ' ' << to[wll[i].xx][wll[i].yy] << '\n';
}
return 0;
}
Compilation message
flood.cpp: In function 'int dfs(int, int)':
flood.cpp:59:22: warning: 'daj' may be used uninitialized in this function [-Wmaybe-uninitialized]
return dfs(daj, -1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
109 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
261 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
309 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
330 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
