oj.uz

Submission #1032516

# Submission time Handle Problem Language Result Execution time Memory
1032516 2024-07-23T22:44:40 Z boyliguanhan Amusement Park (JOI17_amusement_park) C++17
18 / 100
 24 ms 6472 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
namespace joi{
  vector<int>adj[10010],adj2[10010];
  bitset<10010>vis,inthisblok,deepest_path;
  int col[10010],CCcol,depdep=0,depnod,par[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);
    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[1010];
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);
}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1808 KB Output is correct
2 Correct 1 ms 1824 KB Output is correct
3 Correct 1 ms 1824 KB Output is correct
4 Correct 1 ms 2060 KB Output is correct
5 Correct 1 ms 1824 KB Output is correct
6 Correct 1 ms 1820 KB Output is correct
7 Correct 1 ms 1812 KB Output is correct
8 Correct 1 ms 1820 KB Output is correct
9 Correct 1 ms 1828 KB Output is correct
10 Correct 1 ms 1808 KB Output is correct
11 Correct 3 ms 2152 KB Output is correct
12 Correct 1 ms 1896 KB Output is correct
13 Correct 1 ms 1820 KB Output is correct
14 Correct 2 ms 1816 KB Output is correct
15 Correct 2 ms 2260 KB Output is correct
16 Correct 1 ms 1824 KB Output is correct
17 Correct 2 ms 1828 KB Output is correct
18 Correct 2 ms 1824 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5940 KB Output is correct
2 Correct 18 ms 6060 KB Output is correct
3 Correct 19 ms 5916 KB Output is correct
4 Correct 12 ms 4412 KB Output is correct
5 Correct 14 ms 4916 KB Output is correct
6 Correct 12 ms 4884 KB Output is correct
7 Correct 11 ms 4680 KB Output is correct
8 Correct 13 ms 4932 KB Output is correct
9 Correct 12 ms 4928 KB Output is correct
10 Correct 11 ms 4420 KB Output is correct
11 Correct 13 ms 4452 KB Output is correct
12 Correct 10 ms 3880 KB Output is correct
13 Correct 9 ms 3868 KB Output is correct
14 Correct 10 ms 4020 KB Output is correct
15 Correct 13 ms 4408 KB Output is correct
16 Correct 11 ms 4168 KB Output is correct
17 Correct 11 ms 4412 KB Output is correct
18 Correct 11 ms 4916 KB Output is correct
19 Correct 11 ms 4668 KB Output is correct
20 Correct 9 ms 4884 KB Output is correct
21 Correct 9 ms 4936 KB Output is correct
22 Runtime error 12 ms 6472 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1820 KB Output is correct
2 Correct 2 ms 1812 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 3 ms 2376 KB Output is correct
5 Correct 2 ms 2368 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Correct 3 ms 2376 KB Output is correct
8 Correct 2 ms 2372 KB Output is correct
9 Correct 10 ms 5672 KB Output is correct
10 Correct 9 ms 5560 KB Output is correct
11 Correct 9 ms 5872 KB Output is correct
12 Correct 1 ms 1824 KB Output is correct
13 Correct 2 ms 1824 KB Output is correct
14 Correct 0 ms 1824 KB Output is correct
15 Correct 1 ms 1820 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5920 KB Output is correct
2 Correct 23 ms 5900 KB Output is correct
3 Correct 24 ms 5968 KB Output is correct
4 Partially correct 11 ms 4416 KB Partially correct
5 Correct 10 ms 5432 KB Output is correct
6 Partially correct 10 ms 4860 KB Partially correct
7 Correct 11 ms 4928 KB Output is correct
8 Correct 10 ms 4412 KB Output is correct
9 Correct 11 ms 4668 KB Output is correct
10 Incorrect 11 ms 4416 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5916 KB Output is correct
2 Correct 19 ms 6104 KB Output is correct
3 Correct 17 ms 5920 KB Output is correct
4 Incorrect 9 ms 4408 KB Output isn't correct
5 Halted 0 ms 0 KB -