| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 350914 |
2021-01-19T09:50:21 Z |
Hossein29 |
Spiral (BOI16_spiral) |
C++14 |
|
1500 ms |
364 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e3+10;
const int maxm = 2e2+10;
const int inf = 1e9+1;
int n,m,w,h;
int tree[maxn][3]; // x , y , r
int vis[maxm][2]; // e , r
int p[maxn],sz[maxn],l[maxn],r[maxn],t[maxn],b[maxn],block[4][4];
vector<int>G[maxm];
int get_parent(int v){
if(p[v] == v)
return v;
return p[v] = get_parent(p[v]);
}
void make_union(int v,int u, int r1){
int a1 = get_parent(v);
int b1 = get_parent(u);
if(a1 == b1) return;
if((min(abs(r[a1] - l[b1]),abs(r[b1] - l[a1]))) < 2*r1){
if(min(abs(t[b1] - b[a1]),abs(b[b1] - t[a1])) < 2*r1){
if(sz[a1] < sz[b1])
swap(a1,b1);
p[b1] = a1;
sz[a1] += sz[b1];
l[a1] = min(l[a1],l[b1]);
r[a1] = max(r[a1],r[b1]);
t[a1] = max(t[a1],t[b1]);
b[a1] = min(b[a1],b[b1]);
}
}
if(l[a1] == 0 && t[a1] == h) block[1][2] = true;
if(l[a1] == 0 && r[a1] == w) block[1][3] = true;
if(l[a1] == 0 && b[a1] == 0) block[1][4] = true;
if(t[a1] == h && r[a1] == w) block[2][3] = true;
if(t[a1] == h && b[a1] == 0) block[2][4] = true;
if(r[a1] == w && b[a1] == 0) block[3][4] = true;
}
int32_t main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
////////////////////////////////////////////////
cin >> n >> m >> w >> h;
for(int i = 1;i<=n;i++){
cin >> tree[i][0] >> tree[i][1] >> tree[i][2];
}
for(int i = 0;i<m;i++){
cin >> vis[i][0] >> vis[i][1];
for(int j = 1;j<=n;j++){
p[j] = j;
sz[j] = 1;
l[j] = max(0LL,(tree[j][0]-tree[j][2] < 2*vis[i][1] ? 0 : tree[j][0]-tree[j][2]));
r[j] = min(w,(tree[j][0]+tree[j][2] + 2*vis[i][1] <= w ? tree[j][0]+tree[j][2] : w));
t[j] = min(h,(tree[j][1]+tree[j][2] + 2*vis[i][1] <= h ? tree[j][0]+tree[j][2] : h));
b[j] = max(0LL,(tree[j][1]-tree[j][2] - 2*vis[i][1] < 0 ? 0 : tree[j][1]-tree[j][2]));
int a = j;
if(l[a] == 0 && t[a] == h) block[1][2] = true;
if(l[a] == 0 && r[a] == w) block[1][3] = true;
if(l[a] == 0 && b[a] == 0) block[1][4] = true;
if(t[a] == h && r[a] == w) block[2][3] = true;
if(t[a] == h && b[a] == 0) block[2][4] = true;
if(r[a] == w && b[a] == 0) block[3][4] = true;
}
for(int j = 0;j<6;j++){
for(int k = 0;k<6;k++){
block[i][j] = false;
}
}
for(int j = 2;j<=n;j++){
make_union(j,j-1,vis[i][0]);
}
if(vis[i][0] == 1){
G[i].push_back(1);
if(block[1][4] == true) continue;
if(block[1][3] == false && block[1][2] == false) G[i].push_back(4);
if(block[2][4] == false && block[3][4] == false) G[i].push_back(2);
if(block[1][3] == false && block[2][4] == false && block[2][3] == false) G[i].push_back(3);
}
else if(vis[i][1] == 2){
G[i].push_back(2);
if(block[3][4] == true) continue;
if(block[1][4] == false && block[2][4] == false) G[i].push_back(1);
if(block[2][3] == false && block[1][3] == false) G[i].push_back(3);
if(block[1][3] == false && block[2][4] == false && block[1][2] == false) G[i].push_back(4);
}
else if(vis[i][2] == 3){
G[i].push_back(3);
if(block[2][3] == true) continue;
if(block[3][4] == false && block[1][3] == false) G[i].push_back(2);
if(block[2][4] == false && block[1][2] == false) G[i].push_back(4);
if(block[1][4] == false && block[2][4] == false && block[1][3] == false) G[i].push_back(1);
}
else{
G[i].push_back(4);
if(block[1][2] == true) continue;
if(block[1][4] == false && block[1][3] == false) G[i].push_back(1);
if(block[1][3] == false && block[2][4] == false && block[3][4] == false) G[i].push_back(2);
if(block[2][3] == false && block[2][4] == false) G[i].push_back(3);
}
}
for(int i = 0;i<m;i++){
sort(G[i].begin(),G[i].end());
for(int b : G[i])
cout << b;
cout << "\n";
}
return 0;
}
Compilation message
spiral.cpp: In function 'void make_union(long long int, long long int, long long int)':
spiral.cpp:39:44: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
39 | if(l[a1] == 0 && b[a1] == 0) block[1][4] = true;
| ~~~~~~~~~~^
spiral.cpp:41:44: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
41 | if(t[a1] == h && b[a1] == 0) block[2][4] = true;
| ~~~~~~~~~~^
spiral.cpp:42:44: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
42 | if(r[a1] == w && b[a1] == 0) block[3][4] = true;
| ~~~~~~~~~~^
spiral.cpp: In function 'int32_t main()':
spiral.cpp:71:29: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
71 | block[i][j] = false;
| ~~~~~~~~~~~~^~~~~~~
spiral.cpp:69:24: note: within this loop
69 | for(int j = 0;j<6;j++){
| ~^~
spiral.cpp:64:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
64 | if(l[a] == 0 && b[a] == 0) block[1][4] = true;
| ~~~~~~~~~~^
spiral.cpp:66:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
66 | if(t[a] == h && b[a] == 0) block[2][4] = true;
| ~~~~~~~~~~^
spiral.cpp:67:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
67 | if(r[a] == w && b[a] == 0) block[3][4] = true;
| ~~~~~~~~~~^
spiral.cpp:71:27: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
71 | block[i][j] = false;
| ~~~~~~~~~~^
spiral.cpp:71:27: warning: array subscript 5 is above array bounds of 'long long int [4]' [-Warray-bounds]
spiral.cpp:91:25: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
91 | else if(vis[i][2] == 3){
| ~~~~~~~~^
spiral.cpp:101:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
101 | if(block[1][4] == false && block[1][3] == false) G[i].push_back(1);
| ~~~~~~~~~~^
spiral.cpp:102:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
102 | if(block[1][3] == false && block[2][4] == false && block[3][4] == false) G[i].push_back(2);
| ~~~~~~~~~~^
spiral.cpp:102:74: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
102 | if(block[1][3] == false && block[2][4] == false && block[3][4] == false) G[i].push_back(2);
| ~~~~~~~~~~^
spiral.cpp:103:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
103 | if(block[2][3] == false && block[2][4] == false) G[i].push_back(3);
| ~~~~~~~~~~^
spiral.cpp:94:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
94 | if(block[3][4] == false && block[1][3] == false) G[i].push_back(2);
| ~~~~~~~~~~^
spiral.cpp:95:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
95 | if(block[2][4] == false && block[1][2] == false) G[i].push_back(4);
| ~~~~~~~~~~^
spiral.cpp:96:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
96 | if(block[1][4] == false && block[2][4] == false && block[1][3] == false) G[i].push_back(1);
| ~~~~~~~~~~^
spiral.cpp:96:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
96 | if(block[1][4] == false && block[2][4] == false && block[1][3] == false) G[i].push_back(1);
| ~~~~~~~~~~^
spiral.cpp:86:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
86 | if(block[3][4] == true) continue;
| ~~~~~~~~~~^
spiral.cpp:87:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
87 | if(block[1][4] == false && block[2][4] == false) G[i].push_back(1);
| ~~~~~~~~~~^
spiral.cpp:87:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
87 | if(block[1][4] == false && block[2][4] == false) G[i].push_back(1);
| ~~~~~~~~~~^
spiral.cpp:89:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
89 | if(block[1][3] == false && block[2][4] == false && block[1][2] == false) G[i].push_back(4);
| ~~~~~~~~~~^
spiral.cpp:79:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
79 | if(block[1][4] == true) continue;
| ~~~~~~~~~~^
spiral.cpp:81:26: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
81 | if(block[2][4] == false && block[3][4] == false) G[i].push_back(2);
| ~~~~~~~~~~^
spiral.cpp:81:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
81 | if(block[2][4] == false && block[3][4] == false) G[i].push_back(2);
| ~~~~~~~~~~^
spiral.cpp:82:50: warning: array subscript 4 is above array bounds of 'long long int [4]' [-Warray-bounds]
82 | if(block[1][3] == false && block[2][4] == false && block[2][3] == false) G[i].push_back(3);
| ~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1574 ms |
364 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1551 ms |
364 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
