oj.uz

Submission #1077608

# Submission time Handle Problem Language Result Execution time Memory
1077608 2024-08-27T08:18:42 Z vnm06 Amusement Park (JOI17_amusement_park) C++14
18 / 100
 19 ms 6252 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&((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();
}

#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 cnt=0;
int _Move(int t)
{
  cnt++;
  ///if(cnt>500) assert(false);
  return Move(t);
}

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);

  int tot=0;
  while(p!=par[p])
  {
    tot++;
    if(tot>500) assert(false);
      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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1308 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 1 ms 1312 KB Output is correct
4 Correct 1 ms 1312 KB Output is correct
5 Correct 1 ms 1296 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 2 ms 1308 KB Output is correct
8 Correct 0 ms 1312 KB Output is correct
9 Correct 1 ms 1380 KB Output is correct
10 Correct 1 ms 1308 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 1 ms 1308 KB Output is correct
13 Correct 2 ms 1304 KB Output is correct
14 Correct 0 ms 1312 KB Output is correct
15 Correct 2 ms 1312 KB Output is correct
16 Correct 0 ms 1308 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1308 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 6252 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1300 KB Output is correct
2 Correct 1 ms 1304 KB Output is correct
3 Correct 1 ms 1296 KB Output is correct
4 Correct 2 ms 1332 KB Output is correct
5 Correct 2 ms 1336 KB Output is correct
6 Correct 2 ms 1328 KB Output is correct
7 Correct 2 ms 1332 KB Output is correct
8 Correct 2 ms 1336 KB Output is correct
9 Correct 8 ms 2892 KB Output is correct
10 Correct 7 ms 3040 KB Output is correct
11 Correct 7 ms 3032 KB Output is correct
12 Correct 1 ms 1296 KB Output is correct
13 Correct 0 ms 1292 KB Output is correct
14 Correct 0 ms 1308 KB Output is correct
15 Correct 1 ms 1296 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 6232 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 6236 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -