Submission #830143

#	Time	Username	Problem	Language	Result	Execution time	Memory
830143		FEDIKUS	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	26 ms	5532 KiB

Joi

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

using namespace std;
using ll = long long;

namespace{
  const int maxn=10010;
  const int logg=60;

  int boja[maxn];
  int bio[maxn];
  int p[maxn];
  vector<int> g[maxn];
  vector<int> stablo[maxn];
  int deg[maxn];
  set<int> lisce;
  int klk=0;

  bool dfs(int node){
    bio[node]=1;
    klk++;
    boja[node]=klk-1;

    if(klk==60) return true;
    for(int i:g[node]){
      if(bio[i]) continue;
      stablo[node].push_back(i);
      p[i]=node;
      if(dfs(i)) return true;
    }
    return false;
  }

  void dfs2(int node){
    bio[node]=2;
    for(int i:g[node]){
      if(bio[i]==1){
        p[node]=i;
        p[i]=-1;

        dfs2(i);

        p[node]=-1;
        p[i]=node;
      }else if(bio[i]==0){
        int uzimam=-1;
        if(*lisce.begin()==node){
          uzimam=*(++lisce.begin());
        }else uzimam=*lisce.begin();

        boja[i]=boja[uzimam];

        p[node]=i;
        p[i]=-1;

        deg[p[uzimam]]--;
        deg[uzimam]--;
        lisce.erase(uzimam);
        if(deg[p[uzimam]]==1) lisce.emplace(p[uzimam]);
        lisce.emplace(i);
        if(deg[node]==1) lisce.erase(node);
        deg[node]++;
        deg[i]++;
        if(deg[i]==1) lisce.emplace(i);

        dfs2(i);

        if(deg[i]==1) lisce.erase(i);
        deg[node]--;
        deg[i]--;
        if(deg[node]==1) lisce.emplace(node);
        lisce.erase(i);
        if(deg[p[uzimam]]==1) lisce.erase(p[uzimam]);
        lisce.emplace(uzimam);
        deg[uzimam]++;
        deg[p[uzimam]]++;


        p[node]=-1;
        p[i]=node;
      }
    }
  }

}

void Joi(int n, int m, int a[], int b[], ll x, int t) {
  for(int i=0;i<m;i++){
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  p[0]=-1;
  dfs(0);
  for(int i=0;i<n;i++) if(bio[i]==1) for(int j:stablo[i]) deg[i]++,deg[j]++;
  for(int i=0;i<n;i++) if(bio[i]==1 && deg[i]==1) lisce.emplace(i);
  dfs2(0);

  for(int i=0;i<n;i++) MessageBoard(i,((1LL<<boja[i])&x)!=0);
}

Ioi

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

using namespace std;
using ll = long long;

namespace{
  const int maxn=10010;
  const int logg=60;

  int boja[maxn];
  int bio[maxn];
  int p[maxn];
  vector<int> g[maxn];
  vector<int> stablo[maxn];
  int deg[maxn];
  set<int> lisce;
  int klk=0;
  set<int> imam;
  int poc;
  ll res=0;
  set<int> koristio;

  bool dfs(int node){
    bio[node]=1;
    imam.emplace(node);
    klk++;
    boja[node]=klk-1;

    if(klk==60) return true;
    for(int i:g[node]){
      if(bio[i]) continue;
      stablo[node].push_back(i);
      p[i]=node;
      if(dfs(i)) return true;
    }
    return false;
  }

  bool dfs2(int node){

    if(node==poc){
      return true;
    }

    bio[node]=2;
    for(int i:g[node]){
      if(bio[i]==1){
        p[node]=i;
        p[i]=-1;

        if(dfs2(i)) return true;

        p[node]=-1;
        p[i]=node;
      }else if(bio[i]==0){
        int uzimam=-1;
        if(*lisce.begin()==node){
          uzimam=*(++lisce.begin());
        }else uzimam=*lisce.begin();

        assert(lisce.size()>=2);
        
        assert(uzimam!=node);
        assert(p[uzimam]!=uzimam);
        assert(i!=uzimam);

        boja[i]=boja[uzimam];

        p[node]=i;
        p[i]=-1;

        assert(deg[uzimam]==1);
        assert(imam.find(uzimam)!=imam.end());
        imam.erase(uzimam);
        assert(imam.find(i)==imam.end());
        assert(p[uzimam]!=i);
        imam.emplace(i);
        deg[p[uzimam]]--;
        deg[uzimam]--;
        lisce.erase(uzimam);
        assert(deg[p[uzimam]]>0);
        if(deg[p[uzimam]]==1) lisce.emplace(p[uzimam]);
        if(deg[node]==1) lisce.erase(node);
        deg[node]++;
        deg[i]++;
        if(deg[i]==1) lisce.emplace(i);

        if(dfs2(i)) return true;

        if(deg[i]==1) lisce.erase(i);
        deg[i]--;
        deg[node]--;
        if(deg[node]==1) lisce.emplace(node);
        if(deg[p[uzimam]]==1) lisce.erase(p[uzimam]);
        lisce.emplace(uzimam);
        deg[uzimam]++;
        deg[p[uzimam]]++;
        imam.erase(i);
        imam.emplace(uzimam);


        p[node]=-1;
        p[i]=node;
      }
    }
    return false;
  }

  int v;
  int klk2=0;

  void uradi(int node){
    klk2++;
    //assert(koristio.find(boja[node])==koristio.end());
    koristio.emplace(boja[node]);
    res+=(1ll<<boja[node])*v;
    bio[node]=3;
    for(int i:g[node]){
      if(bio[i]==3) continue;
      if(imam.find(i)==imam.end()) continue;

      v=Move(i);
      uradi(i);
      v=Move(node);
    }
  }

}

ll Ioi(int n, int m, int a[], int b[], int _poc, int _v, int t){
  poc=_poc;
  v=_v;
  for(int i=0;i<m;i++){
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  p[0]=-1;
  dfs(0);
  assert(imam.size()==60);
  if(imam.find(poc)==imam.end()){
    for(int i=0;i<n;i++) if(bio[i]==1) for(int j:stablo[i]) deg[i]++,deg[j]++;
    for(int i=0;i<n;i++) if(bio[i]==1 && deg[i]==1) lisce.emplace(i);
    dfs2(0);
  }
  assert(imam.size()==60);
  uradi(poc);
  assert(koristio.size()==60);
  return res;
}

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