oj.uz

Submission #1077462

# Submission time Handle Problem Language Result Execution time Memory
1077462 2024-08-27T07:29:59 Z vnm06 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 24 ms 4616 KB 
#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&(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&(1<<(dpt[i]%60))));
    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();
}

#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];
int tval[10005];
int 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);
  }
}

void euler_tour2(int v)
{
  if(br>=60) return;
  x|=(tval[v]<<tpos[v]);
  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);
  }
  Move(par[v]);
}

int 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;
    bool fl=0;
    for(int i=0; i<60; i++)
    {
      x|=(tval[p]<<tpos[p]);
      if(tpos[p]==59) fl=1;
      if(p==par[p]) break;
      tval[par[p]]=Move(par[p]);
      p=par[p];
    }
    if(fl) return x;
    destn[lastv]=-1;
    while(lastv!=par[lastv])
    {
      destn[par[lastv]]=lastv;
      lastv=par[lastv];
    }
    for(int i=0; i<60; i++)
    {
      x|=(tval[p]<<tpos[p]);
      if(destn[p]==-1) break;
      tval[destn[p]]=Move(destn[p]);
      p=destn[p];
    }
    return x;
  }

  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=destn[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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4568 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4508 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4616 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -