Submission #384869

#	Time	Username	Problem	Language	Result	Execution time	Memory
384869		innocentkitten	Park (BOI16_park)	C++14	0 / 100	2584 ms	66192 KiB

park

#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define H 2021

using namespace std;

typedef pair<long long int,long long int> pii;
typedef pair<pii,int> circ;

int N,M,W,L;
circ C[H]; // nodes 2001, 2002, 2003, 2004 are SENW borders
vector<pii> process;
vector<circ> offline;
int ret[100010];
int S[H];
int P[H];
bool adj[4][4];
bool reach[5][5];

bool sz(circ a, circ b) {
    return a.f.f < b.f.f;
}

bool re(circ a, circ b) {
    return a.s < b.s;
}

int eval(int a, int b) {
    if (b > 2000) return eval(b,a);
    if (a == 2001) return C[b].f.s-C[b].s;
    if (a == 2002) return W-C[b].f.f-C[b].s;
    if (a == 2003) return L-C[b].f.s-C[b].s;
    if (a == 2004) return C[b].f.f-C[b].s;
    return (int)(sqrt((C[a].f.f-C[b].f.f)*(C[a].f.f-C[b].f.f)
    +(C[a].f.s-C[b].f.s)*(C[a].f.s-C[b].f.s))-C[a].s-C[b].s);
    // not sure if they want floor or ceil, so i'm keeping it
    // this way for now
}

bool comp(pii a, pii b){
    return eval(a.f,a.s)<eval(b.f,b.s);
}

int pp(int x) {
	if (P[x]==x) return x;
    return (P[x] = pp(P[x]));
}

void un(int a, int b) {
	a = pp(a);
	b = pp(b);
	if (a == b) return;
	if (S[a] > S[b]) swap(a,b);
	S[b] += S[a];
	P[a] = b;
}

int main() {
    cin>>N>>M>>W>>L;
    for (int i = 0; i < H; i++) {
        S[i] = 1; P[i] = i;
    }
    for (int i = 0; i < N; i++) {
        int a,b,r; cin>>a>>b>>r;
        C[i]=mp(mp(a,b),r);
        for (int j = 2001; j < 2005; j++) {
            process.pb(mp(j,i));
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            process.pb(mp(i,j));
        }
    }
    sort(process.begin(),process.end(),comp);
    for (int i = 0; i < M; i++) {
        int s,p; cin >> s >> p;
        offline.pb(mp(mp(s,p),i));
    }
    sort(offline.begin(),offline.end(),sz);
    int point=0;
    if (N > 1000) throw 1;
    for (int i = 0; i < M; i++) {
        circ quer = offline[i];
        while ((point < process.size())
                && ((eval(process[point].f,process[point].s))
                < 2*quer.f.f)) {
            un(process[point].f,process[point].s);
            point++;
        }
        for (int x = 0; x < 4; x++) {
            for (int y = x+1; y < 4; y++) {
                adj[x][y]=(pp(x+2001)==pp(y+2001));
                adj[y][x]=adj[x][y];
            }
        }
        reach[1][1] = true;
        reach[2][2] = true;
        reach[3][3] = true;
        reach[4][4] = true;
        reach[1][2] = !(adj[0][1]||adj[0][2]||adj[0][3]);
        reach[2][1] = reach[1][2];
        reach[2][3] = !(adj[1][0]||adj[1][2]||adj[1][3]);
        reach[3][2] = reach[2][3];
        reach[3][4] = !(adj[2][0]||adj[2][1]||adj[2][3]);
        reach[4][3] = reach[3][4];
        reach[4][1] = !(adj[3][0]||adj[3][1]||adj[3][2]);
        reach[1][4] = reach[4][1];
        reach[1][3] = !(adj[0][2]||adj[0][3]||adj[1][2]||adj[1][3]);
        reach[3][1] = reach[1][3];
        reach[2][4] = !(adj[0][1]||adj[0][2]||adj[3][1]||adj[3][2]);
        reach[4][2] = reach[2][4];
        for (int x = 1; x < 5; x++) {
            if (reach[quer.f.s][x]) cout << x;
        }
        cout << endl;
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while ((point < process.size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42