oj.uz

Submission #1032518

# Submission time Handle Problem Language Result Execution time Memory
1032518 2024-07-23T22:47:05 Z boyliguanhan Amusement Park (JOI17_amusement_park) C++17
18 / 100
 27 ms 19516 KB 
#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);
}

#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[100100],adj2[100100];
    bitset<100100>vis;
    int col[100100],CCcol,depdep=0,depnod,par[100100],deepest_path[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);
        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 6 ms 10268 KB Output is correct
2 Correct 5 ms 10264 KB Output is correct
3 Correct 5 ms 10800 KB Output is correct
4 Correct 4 ms 10280 KB Output is correct
5 Correct 4 ms 10268 KB Output is correct
6 Correct 5 ms 10280 KB Output is correct
7 Correct 5 ms 10532 KB Output is correct
8 Correct 5 ms 10536 KB Output is correct
9 Correct 5 ms 10528 KB Output is correct
10 Correct 4 ms 10280 KB Output is correct
11 Correct 7 ms 10864 KB Output is correct
12 Correct 4 ms 10508 KB Output is correct
13 Correct 5 ms 10540 KB Output is correct
14 Correct 5 ms 10552 KB Output is correct
15 Correct 4 ms 10340 KB Output is correct
16 Correct 5 ms 10528 KB Output is correct
17 Correct 4 ms 10536 KB Output is correct
18 Correct 5 ms 10600 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14876 KB Output is correct
2 Correct 22 ms 14872 KB Output is correct
3 Correct 27 ms 14920 KB Output is correct
4 Correct 15 ms 13068 KB Output is correct
5 Correct 18 ms 13636 KB Output is correct
6 Correct 17 ms 13376 KB Output is correct
7 Correct 15 ms 13384 KB Output is correct
8 Correct 16 ms 13528 KB Output is correct
9 Correct 17 ms 13380 KB Output is correct
10 Correct 16 ms 13384 KB Output is correct
11 Correct 16 ms 13384 KB Output is correct
12 Correct 14 ms 12848 KB Output is correct
13 Correct 13 ms 12840 KB Output is correct
14 Correct 14 ms 12848 KB Output is correct
15 Correct 16 ms 12884 KB Output is correct
16 Correct 13 ms 12872 KB Output is correct
17 Correct 15 ms 12872 KB Output is correct
18 Correct 16 ms 12872 KB Output is correct
19 Correct 15 ms 12868 KB Output is correct
20 Correct 12 ms 13664 KB Output is correct
21 Correct 13 ms 13648 KB Output is correct
22 Runtime error 18 ms 19516 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 4 ms 10280 KB Output is correct
2 Correct 4 ms 10276 KB Output is correct
3 Correct 4 ms 10272 KB Output is correct
4 Correct 6 ms 10824 KB Output is correct
5 Correct 6 ms 11096 KB Output is correct
6 Correct 5 ms 10832 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 5 ms 10832 KB Output is correct
9 Correct 14 ms 14416 KB Output is correct
10 Correct 13 ms 14308 KB Output is correct
11 Correct 13 ms 14316 KB Output is correct
12 Correct 4 ms 10264 KB Output is correct
13 Correct 4 ms 10264 KB Output is correct
14 Correct 4 ms 10264 KB Output is correct
15 Correct 5 ms 10264 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14232 KB Output is correct
2 Correct 23 ms 14440 KB Output is correct
3 Correct 22 ms 14440 KB Output is correct
4 Partially correct 15 ms 12692 KB Partially correct
5 Correct 17 ms 13792 KB Output is correct
6 Partially correct 16 ms 13348 KB Partially correct
7 Correct 15 ms 13288 KB Output is correct
8 Correct 15 ms 13048 KB Output is correct
9 Correct 16 ms 13292 KB Output is correct
10 Incorrect 14 ms 13024 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14436 KB Output is correct
2 Correct 19 ms 14436 KB Output is correct
3 Correct 19 ms 14432 KB Output is correct
4 Incorrect 12 ms 12764 KB Output isn't correct
5 Halted 0 ms 0 KB -