Submission #1032517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032517		boyliguanhan	Amusement Park (JOI17_amusement_park)	C++17	18 / 100	23 ms	10816 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
namespace joi{
  vector<int>adj[100100],adj2[100100];
  bitset<100100>vis,inthisblok,deepest_path;
  int col[100100],CCcol,depdep=0,depnod,par[100100];
  void dfstree(int n){
    vis[n]=1;
    for(auto i:adj[n]){
      if(!vis[i]) {
        dfstree(i);
        adj2[i].push_back(n);
        adj2[n].push_back(i);
      }
    }
    adj[n].clear();
  }
  void getdeepest(int n,int dep){
    if(dep>depdep)
      depdep=dep,depnod=n;
    for(auto i:adj2[n])
      if(!col[i]&&i-par[n])
        getdeepest(i,dep+1);
  }
  void gowild(int n,int&CC,int color){
    if(!col[n])CC--,col[n]=color;
    if(!CC)return;
    for(auto i:adj2[n])
      if(i-par[n]&&(!col[i]||col[i]==color))
        gowild(i,CC,color);
  }
  void assigncols(int rt,int thecol){
    depdep=0;
    int CC=60;
    getdeepest(rt,1);
    int C=depnod;
    while(C-rt) deepest_path[C]=1,
      CC--,col[C]=thecol,C=par[C];
    gowild(rt,CC,thecol);
  }
  void preproc(int n,int p){
    par[n]=p;
    for(auto i:adj2[n])
      if(i-p)preproc(i,n);
  }
  int dfscol(int n){
    int sz=1;
    for(auto i:adj2[n])
      if(i-par[n])
        sz+=dfscol(i);
    if(sz>=60)
      assigncols(n,++CCcol),sz=0;
    return sz;
  }
}
vector<int>positions[10100];
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  for(int i=0;i<M;i++)
    joi::adj[A[i]+1].push_back(B[i]+1),
    joi::adj[B[i]+1].push_back(A[i]+1);
  joi::dfstree(1);
  joi::preproc(1,0);
  joi::dfscol(1);
  for(int i=1;i<=N;i++) if(joi::col[i])
    positions[joi::col[i]].push_back(i);
  for(int i=1;i<=joi::CCcol;i++){
    long long X2=X;
    for(auto j:positions[i])
      MessageBoard(j-1,X2&1),X2>>=1;
  }
  for(int i=1;i<=N;i++) if(!joi::col[i])
    MessageBoard(i-1,0);
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
bitset<100100>messg;
void gooo(int nod){
    messg[nod]=Move(nod-1);
}
vector<int>path;
namespace ioi{
    vector<int>adj[10010],adj2[10010];
    bitset<10010>vis;
    int col[10010],CCcol,depdep=0,depnod,par[10010],deepest_path[10010];
    void dfstree(int n){
        vis[n]=1;
        for(auto i:adj[n]){
            if(!vis[i]) {
                dfstree(i);
                adj2[i].push_back(n);
                adj2[n].push_back(i);
            }
        }
        adj[n].clear();
    }
    void getdeepest(int n,int dep){
        if(dep>depdep)
            depdep=dep,depnod=n;
        for(auto i:adj2[n])
            if(!col[i]&&i-par[n])
                getdeepest(i,dep+1);
    }
    void gowild(int n,int&CC,int color){
        if(!col[n])CC--,col[n]=color;
        if(!CC)return;
        for(auto i:adj2[n])
            if(i-par[n]&&(!col[i]||col[i]==color))
                gowild(i,CC,color);
    }
    void assigncols(int rt,int thecol){
        depdep=0;
        int CC=60;
        getdeepest(rt,1);
        deepest_path[rt]=1;
        int C=depnod;
        while(C-rt) deepest_path[C]=1,
            CC--,col[C]=thecol,C=par[C];
        gowild(rt,CC,thecol);
    }
    void preproc(int n,int p){
        par[n]=p;
        for(auto i:adj2[n])
            if(i-p)preproc(i,n);
    }
    void makenocol(int n){
        col[n]=-1;
        for(auto i:adj2[n])
            if(i-par[n]&&!col[i])
                makenocol(i);
    }
    int dfscol(int n){
        int sz=1;
        for(auto i:adj2[n])
            if(i-par[n])
                sz+=dfscol(i);
        if(sz>=60)
            assigncols(n,++CCcol),sz=0;
        if(n==1&&sz){
            makenocol(n);
        }
        return sz;
    }
    void tofindall(int n){
        for(auto i:adj2[n])
            if(col[i]==col[n]&&!deepest_path[i]&&i!=par[n])
                gooo(i),tofindall(i);
        if(!deepest_path[n])
            gooo(par[n]);
        else for(auto i:adj2[n])
            if(i-par[n]&&deepest_path[i]&&col[i]==col[n])
                gooo(i),tofindall(i);
    }
    pair<int,int>getclos(int n){
        if(col[n]>0)return{0,n};
        pair<int,int>ans={1e9,1e9};
        for(auto i:adj2[n])
            if(i!=par[n])
                ans=min(ans,getclos(i));
        return {ans.first+1,ans.second};
    }
}

long long Ioi2(int P,int N){
    auto[x,y]=ioi::getclos(P);
    vector<int>path;
    do{
        path.push_back(y);
        y=ioi::par[y];
    }while(y-P);
    reverse(path.begin(),path.end());
    for(auto i:path)
        gooo(P=i);
    ioi::tofindall(P);
    vector<int>important;
    for(int i=1;i<=N;i++)
        if(ioi::col[i]==ioi::col[P])
            important.push_back(i);
    long long ans=0;
    reverse(important.begin(),important.end());
    for(auto i:important)
        ans=ans<<1|messg[i];
    return ans;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i=0;i<M;i++)
        ioi::adj[A[i]+1].push_back(B[i]+1),
        ioi::adj[B[i]+1].push_back(A[i]+1);
    P++;
    messg[P]=V;
    ioi::dfstree(1);
    ioi::preproc(1,0);
    ioi::dfscol(1);
    if(ioi::col[P]==-1){
        return Ioi2(P,N);
    }
    while(!ioi::col[P])
        gooo(P=ioi::par[P]);
    while(ioi::col[ioi::par[P]]==ioi::col[P])
        gooo(P=ioi::par[P]);
    ioi::tofindall(P);
    vector<int>important;
    for(int i=1;i<=N;i++)
        if(ioi::col[i]==ioi::col[P])
            important.push_back(i);
    long long ans=0;
    reverse(important.begin(),important.end());
    for(auto i:important)
        ans=ans<<1|messg[i];
    return ans;
}

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