Submission #1077595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077595		vnm06	Amusement Park (JOI17_amusement_park)	C++14	28 / 100	19 ms	4848 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>

using namespace std;

long long _x;
int _n, _m;
vector<int> _gr[10005];
int _par[10005], _dpt[10005], _root;
bool _used[10005];

queue<int> _qu;

int _br=0;
void _euler_tour(int v)
{
  MessageBoard(v, bool(_x&((long long)1<<(_br%60))));
  _used[v]=1;
  int _brs=_gr[v].size();
  for(int i=0; i<_brs; i++)
  {
    int nv=_gr[v][i];
    if(_used[nv]) continue;
    _br++;
    _euler_tour(nv);
  }
}

void _find_diam()
{
  _qu.push(0);
  _used[0]=1;
  int lastv;


  while(!_qu.empty())
  {
    lastv=_qu.front();
    _qu.pop();
    int _brs=_gr[lastv].size();
    for(int i=0; i<_brs; i++)
    {
      int nv=_gr[lastv][i];
      if(!_used[nv])
      {
        _used[nv]=1;
        _qu.push(nv);
      }
    }
  }
  for(int i=0; i<_n; i++) _used[i]=0;
  _used[lastv]=1;
  _par[lastv]=lastv;
  _root=lastv;
  _qu.push(lastv);

  while(!_qu.empty())
  {
    lastv=_qu.front();
    _qu.pop();
    int _brs=_gr[lastv].size();
    for(int i=0; i<_brs; i++)
    {
      int nv=_gr[lastv][i];
      if(!_used[nv])
      {
        _used[nv]=1;
        _par[nv]=lastv;
        _dpt[nv]=_dpt[lastv]+1;
        _qu.push(nv);
      }
    }
  }

  if(_dpt[lastv]>=59)
  {
    for(int i=0; i<_n; i++) {MessageBoard(i, bool(_x&((long long)1<<(_dpt[i]%60)))); /**cout<<((long long)1<<(_dpt[i]%60))<<endl;*/}
    return;
  }

  int lng=_dpt[lastv]+1, nr=lastv;
  for(int i=1; i<lng/2; i++) nr=_par[nr];
  for(int i=0; i<_n; i++) _used[i]=0;
  _euler_tour(nr);

}

void Joi(int N, int M, int A[], int B[], long long X, int T) 
{
  _n=N;
  _m=M;
  _x=X;
  for(int i=0; i<M; i++)
  {
    _gr[A[i]].push_back(B[i]);
    _gr[B[i]].push_back(A[i]);
  }
  _find_diam();
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

long long x=0;
int n, m, p;
vector<int> gr[10005];
int par[10005], dpt[10005], root;
bool used[10005];
long long tval[10005];
long long tpos[10005];
int destn[10005];

queue<int> qu;

int br=0;
void euler_tour(int v)
{
  tpos[v]=br%60;
  used[v]=1;
  int brs=gr[v].size();
  for(int i=0; i<brs; i++)
  {
    int nv=gr[v][i];
    if(used[nv]) continue;
    par[nv]=v;
    br++;
    euler_tour(nv);
  }
}

bool prikl=0;

void euler_tour2(int v)
{
  x|=(tval[v]<<tpos[v]);
  if(br>=59) return;
  used[v]=1;
  int brs=gr[v].size();
  for(int i=0; i<brs; i++)
  {
    int nv=gr[v][i];
    if(used[nv]) continue;
    br++;
    tval[nv]=Move(nv);
    euler_tour2(nv);
    if(br>=59) return;
  }
  Move(par[v]);
}

long long find_diam()
{
  qu.push(0);
  used[0]=1;
  int lastv;
  while(!qu.empty())
  {
    lastv=qu.front();
    qu.pop();
    int brs=gr[lastv].size();
    for(int i=0; i<brs; i++)
    {
      int nv=gr[lastv][i];
      if(!used[nv])
      {
        used[nv]=1;
        qu.push(nv);
      }
    }
  }
  for(int i=0; i<n; i++) used[i]=0;
  used[lastv]=1;
  par[lastv]=lastv;
  root=lastv;
  qu.push(lastv);

  while(!qu.empty())
  {
    lastv=qu.front();
    qu.pop();
    int brs=gr[lastv].size();
    for(int i=0; i<brs; i++)
    {
      int nv=gr[lastv][i];
      if(!used[nv])
      {
        used[nv]=1;
        par[nv]=lastv;
        dpt[nv]=dpt[lastv]+1;
        qu.push(nv);
      }
    }
  }

  if(dpt[lastv]>=59)
  {
    for(int i=0; i<n; i++) tpos[i]=dpt[i]%60;
    for(int i=0; i<60; i++)
    {
      x|=(tval[p]<<tpos[p]);
      if(p==par[p]) break;
      tval[par[p]]=Move(par[p]);
      p=par[p];
    }
    destn[lastv]=-1;
    //cout<<'d'<<lastv<<endl;
    while(lastv!=par[lastv])
    {
      destn[par[lastv]]=lastv;
      //cout<<lastv<<endl;
      lastv=par[lastv];
    }
    for(int i=0; i<60; i++)
    {
      //cout<<x<<endl;
      x|=(tval[p]<<tpos[p]);
      if(destn[p]==-1) break;
      tval[destn[p]]=Move(destn[p]);
      p=destn[p];
    }
    return x;
  }
  /////cout<<dpt[lastv]<<endl;

  int lng=dpt[lastv]+1, nr=lastv;
  for(int i=1; i<lng/2; i++) nr=par[nr];
  for(int i=0; i<n; i++) used[i]=0;

  par[nr]=nr;
  euler_tour(nr);

  while(p!=par[p])
  {
      x|=(tval[p]<<tpos[p]);
      tval[par[p]]=Move(par[p]);
      p=par[p];
  }
  br=0;
  for(int i=0; i<n; i++) used[i]=0;
  euler_tour2(p);
  return x;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) 
{
  n=N;
  m=M;
  p=P;
  tval[P]=V;
  for(int i=0; i<M; i++)
  {
    gr[A[i]].push_back(B[i]);
    gr[B[i]].push_back(A[i]);
  }
  return find_diam();
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17