| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 121263 |
2019-06-26T09:24:01 Z |
Plurm |
Flood (IOI07_flood) |
C++11 |
|
151 ms |
9452 KB |
#include <bits/stdc++.h>
#define get(a,b) (ev[g[a][b]].first ^ ev[g[a][b]].second ^ a)
using namespace std;
int x[100005];
int y[100005];
int g[100005][4]; // U, L, D, R
class Compare{
public:
bool operator()(int x, int y){
return ::y[x] < ::y[y];
}
};
int prior[4][4] = {
{1, 0, 3, 2}, // U
{2, 1, 0, 3}, // L
{3, 2, 1, 0}, // D
{0, 3, 2, 1}
};
int inv[4] = {2, 3, 0, 1};
bool deleted[200005];
vector<pair<int,int> > ev;
void deleteEdge(int idx){
int u = ev[idx].first;
int v = ev[idx].second;
for(int i = 0; i < 4; i++){
int j = inv[i];
if(get(u,i) == v && get(v,j) == u){
g[u][i] = -1;
g[v][j] = -1;
}
}
}
int main(){
memset(g, -1, sizeof(g));
int n;
scanf("%d",&n);
multiset<int, Compare> ms;
for(int i = 1; i <= n; i++){
scanf("%d%d",x+i,y+i);
}
for(int i = 1; i <= n; i++){
ms.insert(i);
}
int w;
scanf("%d",&w);
for(int i = 0; i < w; i++){
int a,b;
scanf("%d%d",&a,&b);
if(x[a] > x[b]) swap(a,b);
if(y[a] > y[b]) swap(a,b);
if(x[a] < x[b]){
g[a][3] = i;
g[b][1] = i;
}else{
g[a][0] = i;
g[b][2] = i;
}
ev.push_back(make_pair(a,b));
}
while(!ms.empty()){
int c = *ms.begin();
int state = 1;
// 0: Going up
// 1: Going left
// 2: Going down
// 3: Going right
int u = c;
vector<int> tour;
vector<int> edge;
map<int,int> ecnt;
// U L D R
do{
// Trace the border
tour.push_back(u);
for(int i = 0; i < 4; i++){
int chdir = prior[state][i];
if(g[u][chdir] != -1){
state = chdir;
ecnt[g[u][chdir]]++;
edge.push_back(g[u][chdir]);
u = get(u,chdir);
break;
}
}
}while(u != c);
for(int i = 0; i < edge.size(); i++){
int en = edge[i];
deleteEdge(en);
if(ecnt[en] > 1) continue;
deleted[en] = true;
}
for(int i = 0; i < tour.size(); i++){
int cnt = 0;
for(int j = 0; j < 4; j++) if(g[tour[i]][j] != -1) cnt++;
if(cnt == 0) ms.erase(tour[i]);
}
}
vector<int> ans;
for(int i = 0; i < w; i++){
if(!deleted[i]){
ans.push_back(i+1);
}
}
printf("%d\n",ans.size());
for(int i = 0; i < ans.size(); i++){
printf("%d\n",ans[i]);
}
return 0;
}
/*
23
1 1
1 3
1 5
2 3
2 5
2 1
3 2
3 4
7 1
7 5
8 1
8 5
8 3
7 3
4 4
5 4
6 4
4 3
5 3
6 3
4 2
6 2
5 2
25
1 2
2 3
2 4
4 5
4 6
5 10
6 9
9 14
10 14
12 13
13 11
14 13
7 8
18 15
18 21
21 23
22 20
20 17
15 16
16 17
16 19
18 19
19 20
23 22
23 19
*/
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edge.size(); i++){
~~^~~~~~~~~~~~~
flood.cpp:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < tour.size(); i++){
~~^~~~~~~~~~~~~
flood.cpp:104:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n",ans.size());
~~~~~~~~~~^
flood.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ans.size(); i++){
~~^~~~~~~~~~~~
flood.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
flood.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",x+i,y+i);
~~~~~^~~~~~~~~~~~~~~~
flood.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&w);
~~~~~^~~~~~~~~
flood.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
3584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
7600 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
7920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
8556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
9452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
