oj.uz

Submission #535478

# Submission time Handle Problem Language Result Execution time Memory
535478 2022-03-10T11:08:56 Z __Variatto Park (BOI16_park) C++17
0 / 100
 2500 ms 584 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e3+10;
struct pros{
    int x1, y1,x2, y2;
};
int fau[MAX];
int Find(int a){
    if(fau[a]==a)
        return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a, int b){
    fau[Find(a)]=fau[Find(b)];
}
bool prze(pros a, pros b){
    if((max(a.x1, b.x1)>min(a.x2, b.x2)+1 || max(a.y1, b.y1)>min(a.y2, b.y2)+1) || (max(a.x1, b.x1)==min(a.x2, b.x2)+1 && max(a.y1, b.y1)==min(a.y2, b.y2)+1))
        return false;
    return true;
}
int n, m, w, h, x[MAX], y[MAX], r[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>w>>h;
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    while(m--){
        int pro, e;
        cin>>pro>>e;
        for(int i=1; i<=n+4; i++)
            fau[i]=i;
        for(int i=1; i<=n; i++){
            if(y[i]-(r[i]+pro-1)<=pro) Union(i, n+1);
            if(x[i]+(r[i]+pro-1)>=w-(pro)) Union(i, n+2);
            if(y[i]+(r[i]+pro-1)>=h-(pro)) Union(i, n+3);
            if(x[i]-(r[i]+pro-1)<=pro) Union(i, n+4);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                pros a, b;
                a.x1=x[i]-(r[i]+pro-1), a.y1=y[i]-(r[i]+pro-1), a.x2=x[i]+(r[i]+pro-1), a.y2=y[i]+(r[i]+pro-1);
                b.x1=x[j]-(r[j]+pro-1), b.y1=y[j]-(r[j]+pro-1), b.x2=x[j]+(r[j]+pro-1), b.y2=y[j]+(r[j]+pro-1);
//                cout<<i<<" "<<j<<":  "<<a.x1<<" "<<a.y1<<" "<<a.x2<<" "<<a.y2<<"   "<<b.x1<<" "<<b.y1<<" "<<b.x2<<" "<<b.y2<<"  "<<prze(a, b)<<"\n";
                if(prze(a, b)) Union(i, j);
            }
        }
/*        for(int i=1; i<=n+4; i++)
            cout<<i<<" "<<Find(i)<<"\n";
*/        if(e==1){
            cout<<1;
            if(Find(n+1)!=Find(n+4)&&Find(n+1)!=Find(n+2)&&Find(n+1)!=Find(n+3))
                cout<<2;
            if(Find(n+1)!=Find(n+4)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+3)&&Find(n+2)!=Find(n+3))
                cout<<3;
            if(Find(n+1)!=Find(n+4)&&Find(n+3)!=Find(n+4)&&Find(n+2)!=Find(n+4))
                cout<<4;
        }
        if(e==2){
            if(Find(n+1)!=Find(n+4)&&Find(n+1)!=Find(n+2)&&Find(n+1)!=Find(n+3))
                cout<<1;
            cout<<2;
            if(Find(n+1)!=Find(n+2)&&Find(n+3)!=Find(n+2)&&Find(n+2)!=Find(n+4))
                cout<<3;
            if(Find(n+1)!=Find(n+3)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+2)&&Find(n+4)!=Find(n+3))
                cout<<4;
        }
        if(e==3){
            if(Find(n+1)!=Find(n+4)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+3)&&Find(n+2)!=Find(n+3))
                cout<<1;
            if(Find(n+1)!=Find(n+2)&&Find(n+3)!=Find(n+2)&&Find(n+2)!=Find(n+4))
                cout<<2;
            cout<<3;
            if(Find(n+3)!=Find(n+4)&&Find(n+4)!=Find(n+1)&&Find(n+2)!=Find(n+4))
                cout<<4;
        }
        if(e==4){
            if(Find(n+1)!=Find(n+4)&&Find(n+3)!=Find(n+4)&&Find(n+2)!=Find(n+4))
                cout<<1;
            if(Find(n+1)!=Find(n+3)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+2)&&Find(n+4)!=Find(n+3))
                cout<<2;
            if(Find(n+3)!=Find(n+4)&&Find(n+4)!=Find(n+1)&&Find(n+2)!=Find(n+4))
                cout<<3;
            cout<<4;
        }
        cout<<"\n";

    }

}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 340 KB Output is correct
2 Incorrect 21 ms 352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2563 ms 584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 340 KB Output is correct
2 Incorrect 21 ms 352 KB Output isn't correct
3 Halted 0 ms 0 KB -