oj.uz

Submission #282095

# Submission time Handle Problem Language Result Execution time Memory
282095 2020-08-24T02:37:41 Z NaimSS Park (BOI16_park) C++14
27 / 100
 2500 ms 6772 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}


struct query{
  int r,e,id;
  query(){}
  query(int r,int e,int id):r(r),e(e),id(id){}
};
const int N = 2020;

struct DSU{
  vi p , ps;
  DSU(int n){
    p = vi(n+1),ps = vi(n+1,1);
    rep(i,0,n+1) p[i] = i;
  }
  int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
  bool join(int x , int y){
    x = find(x) , y = find(y);
    if(x == y) return 0;
    if(ps[x] > ps[y]) swap(x,y);
    p[x] = y, ps[y] += ps[x];
    return 1;
  }
};  

ll sq(ll x){return x*x;}

pii Par[5];
string res[100100];
int x[N],y[N],r[N];
int32_t main(){
  fastio;
  int n,m;
  cin >> n >> m;
  int w,h;
  cin >> w >> h;
  Par[1] = pii(0,1);
  Par[2] = pii(w,0);
  Par[3] = pii(h,1);
  Par[4] = pii(0,0);
  DSU dsu(n + 4);
  for(int i=1;i<=n;i++){
    cin >> x[i] >> y[i] >> r[i];
  }

  vector<query> qry;
  for(int i=0;i<m;i++){
    int r,e;
    cin >> r >> e;
    qry.pb(query(r,e,i));
  }
  
  for(auto pessoa : qry){
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        if(sq(r[i] + r[j] + 2*pessoa.r) > sq(x[i] - x[j]) + sq(y[i] - y[j]))dsu.join(i,j);
      }
      if(x[i]-r[i]-pessoa.r*2<0)dsu.join(i,n+4);
      if(y[i]-r[i]-pessoa.r*2<0)dsu.join(i,n+1);
      if(x[i]+r[i]+pessoa.r*2>w)dsu.join(i,n+2);
      if(y[i]+r[i]+pessoa.r*2>h)dsu.join(i,n+3);
    }
   
    int e = pessoa.e;
    string good = "";
    for(int c=1;c<=4;c++){
      if(c==e){
        good+=char('0' + c);
        continue;
      }
      // check if vertical blocks:
      int A = e,B = c;
      if(A > B)swap(A,B);
      int op1 = (A==1 and B==4);
      int op2 = (A==2 and B==3);
      if(!op1 and !op2){
        if(dsu.find(n + 1) == dsu.find(n + 3))continue;
      }

      op1 = (A == 1 and B == 2);
      op2 = (A == 3 and B == 4);

      // check if horizontal blocks:
      if(!op1 and !op2){
        if(dsu.find(n+2)==dsu.find(n+4))continue;
      }

      int prv = (c==1 ? 4 : c-1) + n;
      
      if(dsu.find(n + c) == dsu.find(prv))continue;
      good+=char('0' + c);
    }
    sort(all(good));
    res[pessoa.id] = good;
    cout << good << endl;
  }

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3584 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 6 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 14 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 2 ms 3456 KB Output is correct
10 Correct 2 ms 3456 KB Output is correct

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3584 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 6 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 14 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 2 ms 3456 KB Output is correct
10 Correct 2 ms 3456 KB Output is correct
11 Execution timed out 2597 ms 6772 KB Time limit exceeded
12 Halted 0 ms 0 KB -