#include <bits/stdc++.h>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>
// Including tree_order_statistics_node_update
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using ll = long long;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
class DSU{
public:
vi parents;
vi sizes;
//vector<vector<boolean>> status;
DSU(int size)
{
vi temp(size+4);
parents=temp;
//vector<vector<boolean>> temp2(size);
//status=temp2;
vi temp2(size+4);
for(int i=0; i<size+4; i++)
{
parents[i]=-1;
temp2[i]=1;
}
sizes=temp2;
}
int find(int x)
{
if(parents[x]==-1)
return x;
parents[x]=find(parents[x]);
return parents[x];
}
bool join(int x, int y)
{
//cout<<"JOIN "<<x<<' '<<y<<endl;
x=find(x);
y=find(y);
if(x==y)
return false;
if(sizes[x]<sizes[y])
{
int z=x;
x=y; y=z;
}
parents[y]=x;
sizes[x]+=sizes[y];
return true;
}
bool connected(int x, int y)
{
//cout<<x<<' '<<y<<endl;
return find(x)==find(y);
}
};
string print(vi item)
{
for(int i=0; i<item.size(); i++)
cout<<item[i]<<' ';
return "";
}
int main() {
int n, m; cin>>n>>m;
int w, h; cin>>w>>h;
vi temp(3);
vector<vector<int>> trees(n, temp);
for(int i=0; i<n; i++)
cin>>trees[i][2]>>trees[i][0]>>trees[i][1];
vector<vi> visitors(m, temp); //radius, 1, entrance, i
for(int i=0; i<m; i++){
cin>>visitors[i][0]>>visitors[i][2];
visitors[i][3]=i; visitors[i][1]=1;
}
priority_queue<vi> que; //radius, type, (entrance, i)/(a, b)
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
{
vi entry(4);
entry[0]=-1*((trees[i][0]-trees[j][0])*(trees[i][0]-trees[j][0])
+(trees[i][1]-trees[j][1])*(trees[i][1]-trees[j][1])
-(trees[i][2]+trees[j][2])*(trees[i][2]+trees[j][2]));
entry[1]=0;
entry[2]=i;
entry[3]=j;
que.push(entry);
}
for(int i=0; i<n; i++) //top = 0, right = 1, down = 2, left = 3
{
vi entry(4);
entry[0]=-1*((h-trees[i][1]-trees[i][2])*(h-trees[i][1]-trees[i][2]));
entry[1]=0;
entry[2]=i;
entry[3]=n;
que.push(entry);
entry[0]=-1*(w-trees[i][0]-trees[i][2])*(w-trees[i][0]-trees[i][2]);
entry[3]=n+1;
que.push(entry);
entry[0]=-1*(trees[i][1]-trees[i][2])*(trees[i][1]-trees[i][2]);
entry[3]=n+2;
que.push(entry);
entry[0]=-1*(trees[i][0]-trees[i][2])*(trees[i][0]-trees[i][2]);
entry[3]=n+3;
que.push(entry);
}
for(int i=0; i<m; i++)
{
vi entry(4);
entry[0]=-1*visitors[i][0]*visitors[i][0]*4;
entry[1]=visitors[i][1];
entry[2]=visitors[i][2];
entry[3]=visitors[i][3];
que.push(entry);
}
for(int i=0; i<4; i++)
trees.pb(vi{n+i});
vi sol(m);
DSU dsu(n+4);
vector<bool> vb(4);
vector<vector<bool>> match(4, vb);
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
match[i][j]=true;
vector<vector<bool>> dead(4, vb);
for(int i=0; i<4; i++)
dead[i][i]=true;
/*while(que.size()>0){
vi it = que.top();
que.pop();
cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<' '<<it[3]<<endl;
}*/
while(que.size()>0)
{
vi it = que.top();
que.pop();
if(it[1]==0){
//cout<<"Started 0:"<<endl;
//cout<<print(it)<<endl;
//cout<<print(trees[it[2]])<<" | "<<print(trees[it[3]])<<endl;
dsu.join(it[2], it[3]);
if(dsu.connected(n+0,n+2))
{
vector<vector<bool>> held=match;
match=dead;
match[0][3]=held[0][3];
match[1][2]=held[1][2];
}
if(dsu.connected(n+1,n+3))
{
vector<vector<bool>> held=match;
match=dead;
match[2][3]=held[2][3];
match[0][1]=held[0][1];
}
if(dsu.connected(n+0,n+1)) //3
{
for(int i=0; i<4; i++)
{
if(i==2)
continue;
match[min(i,2)][max(i,2)]=false;
}
}
if(dsu.connected(n+1,n+2)) //2
{
for(int i=0; i<4; i++)
{
if(i==1)
continue;
match[min(i,1)][max(i,1)]=false;
}
}
if(dsu.connected(n+2,n+3)) //1
{
for(int i=0; i<4; i++)
{
if(i==0)
continue;
match[min(i,0)][max(i,0)]=false;
}
}
if(dsu.connected(n+3,n+0)) //4
{
for(int i=0; i<4; i++)
{
if(i==3)
continue;
match[min(i,3)][max(i,3)]=false;
}
}
/*for(int i=0; i<4; i++){
for(int j=i; j<4; j++)
cout<<match[i][j]<<' ';
cout<<endl;
}
cout<<"Finished"<<endl;*/
}
if(it[1]==1) //top = 0, right = 1, bottom = 2, left = 3
{
//cout<<"Started 1 :" <<endl;
/*for(int i=0; i<4; i++){
for(int j=i; j<4; j++)
cout<<match[i][j]<<' ';
cout<<endl;
}*/
int enter=it[2]-1;
int out=0;
for(int i=0; i<4; i++)
if(match[min(enter, i)][max(enter, i)])
out=out*10+(i+1);
sol[it[3]]=out;
//cout<<"Finished"<<endl;
}
}
for(int i=0; i<m; i++)
cout<<sol[i]<<'\n';
cout<<endl;
}
Compilation message
park.cpp: In function 'std::string print(vi)':
park.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0; i<item.size(); i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2565 ms |
110504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
13944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2565 ms |
110504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
