Submission #350914

#	Time	Username	Problem	Language	Result	Execution time	Memory
350914		Hossein29	Spiral (BOI16_spiral)	C++14	0 / 100	1574 ms	364 KiB

spiral

#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 (stderr)

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);
      |                                        ~~~~~~~~~~^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25