oj.uz

Submission #916723

# Submission time Handle Problem Language Result Execution time Memory
916723 2024-01-26T11:36:28 Z edogawa_something Amusement Park (JOI17_amusement_park) C++17
0 / 100
 177 ms 262144 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll MM=10101;
const ll inf=2e18;
vii v[MM],adj[MM];
struct dsu{
  ll sz[MM],pa[MM];
  set<ll>elem[MM];
  void init(ll x){
    for(int i=0;i<=x;i++)
    pa[i]=i,sz[i]=1,elem[i].insert(i);
  }
  ll get(ll x){
    if(x==pa[x])
    return x;
    return pa[x]=get(pa[x]);
  }
  bool unite(ll x,ll y){
    x=get(x),y=get(y);
    if(x==y)
    return 1;
    if(sz[x]>sz[y])
    swap(x,y);
    pa[x]=y;
    for(auto it:elem[x])
    elem[y].insert(it);
    sz[y]+=sz[x];
    return 0;
  }
}d,dd;
bool vis[MM];
void partition(ll x,ll pa){
  for(auto it:v[x]){
  if(it==pa)
  continue;
  if(dd.sz[dd.get(x)]==60){
    partition(it,x);
  }
  else{
    dd.unite(it,x);
    partition(it,x);
  }
  }
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
  for(int i=0;i<m;i++){
    v[A[i]].pb(B[i]),v[B[i]].pb(A[i]);
  }
  d.init(n);
  dd.init(n);
  for(int i=0;i<n;i++)
  sort(all(v[i]));
  for(int i=0;i<n;i++){
    for(auto it:v[i]){
      if(!d.unite(i,it))
      adj[i].pb(it),adj[it].pb(i);
    }
  }
  partition(0,-1);
  for(int i=0;i<n;i++){
    if(vis[i])
    continue;
    ll cnt=0;
    for(auto it:dd.elem[dd.get(i)]){
      vis[it]=1;
      MessageBoard(it,bool((X&(1ll<<cnt))>0));
      cnt++;
    }
  }
}

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const ll MM=10101;
const ll inf=2e18;
vii vi[MM],adji[MM];
struct dsu{
  ll sz[MM],pa[MM];
  set<ll>elem[MM];
  void init(ll x){
    for(int i=0;i<=x;i++)
    pa[i]=i,sz[i]=1,elem[i].insert(i);
  }
  ll get(ll x){
    if(x==pa[x])
    return x;
    return pa[x]=get(pa[x]);
  }
  bool unite(ll x,ll y){
    x=get(x),y=get(y);
    if(x==y)
    return 1;
    if(sz[x]>sz[y])
    swap(x,y);
    pa[x]=y;
    for(auto it:elem[x])
    elem[y].insert(it);
    sz[y]+=sz[x];
    return 0;
  }
  bool same(ll x,ll y){
    return (get(x)==get(y));
  }
}di,ddi;
bool visi[MM];
void partitioni(ll x,ll pa){
  for(auto it:vi[x]){
  if(it==pa)
  continue;
  if(ddi.sz[ddi.get(x)]==60){
    partitioni(it,x);
  }
  else{
    ddi.unite(it,x);
    partitioni(it,x);
  }
  }
}
ll parent[MM];
void dfs(ll x=0){
  for(auto it:adji[x]){
    if(it==parent[x])
    continue;
    parent[it]=x;
    dfs(it);
  }
}
ll a[MM];
vector<ll>vv;
void ddfs(ll x,ll pa=-1){
  if(vv.size()==60)
  return;
  vv.pb(x);
  for(auto it:adji[x]){
    if(vv.size()==60)
    return;
    if(it==pa)
    continue;
    if(!ddi.same(it,x)){
    continue;
    }
    ll val=Move(it);
    a[it]=val;
    ddfs(it,x);
  }
  if(vv.size()==60)
  return;
  Move(pa);
}
ll n,m;
ll Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  n=N,m=M;
  for(int i=0;i<m;i++){
    vi[A[i]].pb(B[i]),vi[B[i]].pb(A[i]);
  }
  di.init(n);
  ddi.init(n);
  for(int i=0;i<n;i++)
  sort(all(vi[i]));
  for(int i=0;i<n;i++){
    for(auto it:vi[i]){
      if(!di.unite(i,it))
      adji[i].pb(it),adji[it].pb(i);
    }
  }
  partitioni(0,-1);
  dfs();
  a[P]=V;
  while(ddi.sz[ddi.get(P)]<60){
    P=parent[P],a[P]=Move(parent[P]);
  }
  ddfs(P);
  sort(all(vv));
  ll ans=0;
  for(int i=0;i<n;i++)
  for(ll i=0;i<vv.size();i++){
    ans|=(a[vv[i]])*(1ll<<i);
  }
  return ans;
}

Compilation message

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:113:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(ll i=0;i<vv.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4368 KB Output is correct
2 Incorrect 2 ms 4372 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4384 KB Output is correct
2 Correct 2 ms 4380 KB Output is correct
3 Incorrect 2 ms 4372 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -