제출 #1360042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360042		CowTheCow	Park (BOI16_park)	C++20	100 / 100	1759 ms	72004 KiB

park

#include <bits/stdc++.h>

#define int long long
#define double long double
#define vi vector<int>
#define pb push_back
#define sz(a) a.size()
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()

using namespace std;

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

const int MAXN=2010;
const int MAXQ=1e5+5;

int n,q;
double h,w;

double x [MAXN];
double y [MAXN];
double r [MAXN];

int connected [5][5];
int sizes [MAXN];
int rep [MAXN];
string res [MAXQ];

void build(int s) { 
    for(int i=1;i<=s;i++) {
        sizes[i]=1;
        rep[i]=i;
    }
}

int find(int v) {
    if(rep[v]==v)
        return v;
    rep[v]=find(rep[v]);
    return rep[v];
}

bool unite(int u, int v) {
    int pu=find(u);
    int pv=find(v);
    if(pu==pv) return false;
    if(sizes[pu]<sizes[pv]) swap(pu,pv);

    sizes[pu]+=sizes[pv];
    rep[pv]=pu;
    return true;
}

int square(int v) {
    return v*v;
}

void solve() {
    cin>>n>>q;
    cin>>w>>h;

    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            connected[i][j]=1;

    for(int i=1;i<=n;i++) {
        cin>>x[i]>>y[i]>>r[i];
    }

    vector<tuple<double,int,int>> edges;
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            edges.pb({(double)sqrt((double)square(x[i]-x[j])+(double)square(y[i]-y[j]))-r[i]-r[j],i,j});
        }
    }
    sort(all(edges));

    vector<tuple<int,int,int>> queries;
    for(int i=1;i<=q;i++) {
        int qr,e;
        cin>>qr>>e;
        queries.pb({qr,e,i});
    }
    sort(all(queries));

    build(n+4); //nodes n+1,n+2,n+3,n+4 will be the borders 

    int ord [4] {3,2,1,4};
    int ptr=0;
    for(auto [qr, e, idx]:queries) {
        //check each tree border
        for(int i=1;i<=n;i++) {
            if(x[i]-r[i]-2.0*qr<0.0) {
                unite(i,n+4);
            }
            if(x[i]+r[i]+2.0*qr>w) {
                unite(i,n+2);
            }
            if(y[i]-r[i]-2.0*qr<0.0) {
                unite(i,n+3);
            }
            if(y[i]+r[i]+2.0*qr>h) {
                unite(i,n+1);
            }
        }
        while(ptr<sz(edges)&&get<0>(edges[ptr])<2.0*qr) {
            unite(get<1>(edges[ptr]), get<2>(edges[ptr]));
            ptr++;
        }
        if(find(n+1)==find(n+3)) {
            connected[1][2]=0;
            connected[1][3]=0;
            connected[2][4]=0;  
            connected[3][4]=0;
        }   
        if(find(n+2)==find(n+4)) {
            connected[1][4]=0;  
            connected[1][3]=0;
            connected[2][3]=0;
            connected[2][4]=0;
        }
        for(int j=0;j<4;j++) {
            int tar=ord[j];
            if(find(n+1+j)==find(n+1+((j+1)%4))) {
                for(int k=1;k<=4;k++)
                    connected[min(tar,k)][max(tar,k)]=0;
            }
        }
        string ans="";
        for(int i=1;i<=4;i++) {
            if(i==e||connected[min(i,e)][max(i,e)]) {
                ans+=to_string(i);
            }
        }
        res[idx]=ans;
    }

    for(int i=1;i<=q;i++)
        cout<<res[i]<<"\n";
}  

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;
    // cin>>t;

    while(t>0) {
        solve();
        t--;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'void setIO(std::string)':
park.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 27 / 27
• 서브태스크 2: 31 / 31
• 서브태스크 3: 42 / 42