| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199656 |
2020-02-02T12:56:21 Z |
sjimed |
Flood (IOI07_flood) |
C++14 |
|
532 ms |
26208 KB |
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const long long INF = 1e18;
const int inf = 1e9;
int n, m;
pii a[100010];
vector<pii> x, y;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int con[400010][4];
int w[400010][4];
int chk[400010];
deque<pii> dq;
bool ans[400010];
int main() {
fast;
cin >> n;
x.eb(-1, -1);
for(int i=1; i<=n; i++) {
cin >> a[i].fi >> a[i].se;
for(int k=0; k<4; k++) {
x.eb(a[i].fi + k/2, a[i].se + k%2);
}
}
y = x;
sort(all(x));
x.erase(unique(all(x)), x.end());
sort(all(y));
y.erase(unique(all(y)), y.end());
sort(all(y), [](pii i, pii j) {
return i.se != j.se ? i.se < j.se : i.fi < j.fi;
});
for(int i=0; i<x.size(); i++) {
if(i > 0 && x[i-1].fi == x[i].fi) {
con[i][3] = i-1;
}
if(i+1 < x.size() && x[i].fi == x[i+1].fi) {
con[i][2] = i+1;
}
}
for(int i=0; i<y.size(); i++) {
if(i > 0 && y[i-1].se == y[i].se) {
con[lower_bound(all(x), y[i]) - x.begin()][1] = lower_bound(all(x), y[i-1]) - x.begin();
}
if(i+1 < y.size() && y[i].se == y[i+1].se) {
con[lower_bound(all(x), y[i]) - x.begin()][0] = lower_bound(all(x), y[i+1]) - x.begin();
}
}
cin >> m;
for(int i=1; i<=m; i++) {
int u, v;
cin >> u >> v;
if(a[u] > a[v]) swap(u, v);
if(a[u].fi != a[v].fi) {
w[lower_bound(all(x), mp(a[u].fi+1, a[u].se)) - x.begin()][2] = i;
w[lower_bound(all(x), mp(a[u].fi+1, a[u].se+1)) - x.begin()][3] = i;
w[lower_bound(all(x), mp(a[v].fi, a[v].se)) - x.begin()][2] = i;
w[lower_bound(all(x), mp(a[v].fi, a[v].se+1)) - x.begin()][3] = i;
}
else {
//cout << "????????????????" << a[u].fi << " " << a[u].se << " " << a[v].fi << " " << a[v].se << endl;
w[lower_bound(all(x), mp(a[u].fi, a[u].se+1)) - x.begin()][0] = i;
w[lower_bound(all(x), mp(a[u].fi+1, a[u].se+1)) - x.begin()][1] = i;
w[lower_bound(all(x), mp(a[v].fi, a[v].se)) - x.begin()][0] = i;
w[lower_bound(all(x), mp(a[v].fi+1, a[v].se)) - x.begin()][1] = i;
}
}
/*for(int i=1; i<x.size(); i++) {
cout << "(" << x[i].fi << " " << x[i].se << ") : ";
for(int j=0; j<4; j++) {
cout << "(" << x[con[i][j]].fi << " " << x[con[i][j]].se << ", " << w[i][j] << ") ";
}
cout << endl;
}*/
for(int i=1; i<x.size(); i++) {
if(chk[i]) continue;
dq.eb(i, 1);
while(dq.size()) {
int h = dq.front().fi;
int cost = dq.front().se;
dq.pop_front();
if(chk[h]) continue;
chk[h] = cost;
//cout << "-----> " << x[h].fi << " " << x[h].se << " " << chk[h] << endl;
for(int i=0; i<4; i++) {
if(con[h][i] == 0 || chk[con[h][i]]) continue;
if(w[h][i]) dq.eb(con[h][i], chk[h]+1);
else dq.emplace_front(con[h][i], chk[h]);
}
}
}
for(int i=1; i<x.size(); i++) {
//cout << x[i].fi << " " << x[i].se << " : " << chk[i] << endl;
for(int j=0; j<4; j++) {
if(con[i][j] > 0 && chk[con[i][j]] == chk[i]) ans[w[i][j]] = true;
}
}
int cnt = 0;
for(int i=1; i<=m; i++) {
if(ans[i]) cnt++;
}
cout << cnt << "\n";
for(int i=1; i<=m; i++) {
if(ans[i]) cout << i << "\n";
}
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<x.size(); i++) {
~^~~~~~~~~
flood.cpp:61:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1 < x.size() && x[i].fi == x[i+1].fi) {
~~~~^~~~~~~~~~
flood.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<y.size(); i++) {
~^~~~~~~~~
flood.cpp:72:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1 < y.size() && y[i].se == y[i+1].se) {
~~~~^~~~~~~~~~
flood.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<x.size(); i++) {
~^~~~~~~~~
flood.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<x.size(); i++) {
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
408 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
480 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
6612 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
18776 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
21856 KB |
Output is correct |
| 2 |
Incorrect |
524 ms |
25904 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
26208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
532 ms |
24928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
