oj.uz

Submission #1032760

# Submission time Handle Problem Language Result Execution time Memory
1032760 2024-07-24T08:06:58 Z boyliguanhan Amusement Park (JOI17_amusement_park) C++17
100 / 100
 27 ms 14896 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);
            }
        }
    }
    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(!CC)return;
        if(!col[n])CC--,col[n]=color;
        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;
void deassert(int n){
    if(!n)Move(-1);
}
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);
            }
        }
    }
    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(!CC)return;
        if(!col[n])CC--,col[n]=color;
        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);
    }
    int frm[100100];
    vector<int>getclos(int n){
        vis.reset();
        vis[n]=1;
        queue<int>q;
        q.push(n);
        int ANS;
        while(1){
            int x=q.front();
            q.pop();
            if(col[x]>0){
                ANS=x;
                break;
            }
            for(auto i:adj[x])
                if(!vis[i])vis[i]=1,
                    frm[i]=x,q.push(i);
        }
        vector<int>ans;
        while(ANS-n)
            ans.push_back(ANS),ANS=frm[ANS];
        reverse(ans.begin(),ans.end());
        return ans;
    }
}

long long Ioi2(int P,int N){
    vector<int>path=ioi::getclos(P);
    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=1;i<=N;i++)
        ioi::adj[i].clear(),ioi::adj2[i].clear();
    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);
    deassert(ioi::vis.count()==N);
    deassert(ioi::CCcol>=1);
    for(int i=2;i<=N;i++)
        if(!ioi::par[i])
            return 34;
    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;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:135:30: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |     deassert(ioi::vis.count()==N);
      |              ~~~~~~~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10264 KB Output is correct
2 Correct 5 ms 10268 KB Output is correct
3 Correct 4 ms 10284 KB Output is correct
4 Correct 5 ms 10288 KB Output is correct
5 Correct 4 ms 10280 KB Output is correct
6 Correct 5 ms 10268 KB Output is correct
7 Correct 5 ms 10544 KB Output is correct
8 Correct 4 ms 10544 KB Output is correct
9 Correct 4 ms 10284 KB Output is correct
10 Correct 4 ms 10268 KB Output is correct
11 Correct 6 ms 10968 KB Output is correct
12 Correct 4 ms 10268 KB Output is correct
13 Correct 5 ms 10524 KB Output is correct
14 Correct 4 ms 10540 KB Output is correct
15 Correct 5 ms 10536 KB Output is correct
16 Correct 3 ms 10276 KB Output is correct
17 Correct 4 ms 10284 KB Output is correct
18 Correct 4 ms 10276 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14704 KB Output is correct
2 Correct 23 ms 14884 KB Output is correct
3 Correct 19 ms 14888 KB Output is correct
4 Correct 13 ms 12868 KB Output is correct
5 Correct 14 ms 13788 KB Output is correct
6 Correct 15 ms 13376 KB Output is correct
7 Correct 14 ms 13408 KB Output is correct
8 Correct 13 ms 13376 KB Output is correct
9 Correct 16 ms 13632 KB Output is correct
10 Correct 12 ms 12876 KB Output is correct
11 Correct 12 ms 12876 KB Output is correct
12 Correct 13 ms 12836 KB Output is correct
13 Correct 13 ms 12652 KB Output is correct
14 Correct 13 ms 12848 KB Output is correct
15 Correct 13 ms 12796 KB Output is correct
16 Correct 14 ms 12868 KB Output is correct
17 Correct 14 ms 12872 KB Output is correct
18 Correct 13 ms 12876 KB Output is correct
19 Correct 14 ms 12872 KB Output is correct
20 Correct 11 ms 13896 KB Output is correct
21 Correct 12 ms 13376 KB Output is correct
22 Correct 17 ms 13636 KB Output is correct
23 Correct 14 ms 13380 KB Output is correct
24 Correct 15 ms 13384 KB Output is correct
25 Correct 15 ms 13388 KB Output is correct
26 Correct 17 ms 13388 KB Output is correct
27 Correct 19 ms 13376 KB Output is correct
28 Correct 15 ms 13392 KB Output is correct
29 Correct 14 ms 13360 KB Output is correct
30 Correct 15 ms 13468 KB Output is correct
31 Correct 4 ms 10272 KB Output is correct
32 Correct 5 ms 10468 KB Output is correct
33 Correct 4 ms 10548 KB Output is correct
34 Correct 4 ms 10288 KB Output is correct
35 Correct 4 ms 10280 KB Output is correct
36 Correct 4 ms 10288 KB Output is correct
37 Correct 4 ms 10500 KB Output is correct
38 Correct 5 ms 10532 KB Output is correct
39 Correct 4 ms 10252 KB Output is correct
40 Correct 5 ms 10452 KB Output is correct
41 Correct 4 ms 10284 KB Output is correct
42 Correct 4 ms 10280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10280 KB Output is correct
2 Correct 5 ms 10280 KB Output is correct
3 Correct 4 ms 10268 KB Output is correct
4 Correct 5 ms 11080 KB Output is correct
5 Correct 6 ms 11080 KB Output is correct
6 Correct 6 ms 10832 KB Output is correct
7 Correct 8 ms 11088 KB Output is correct
8 Correct 6 ms 10820 KB Output is correct
9 Correct 12 ms 14404 KB Output is correct
10 Correct 13 ms 14400 KB Output is correct
11 Correct 13 ms 14376 KB Output is correct
12 Correct 4 ms 10276 KB Output is correct
13 Correct 5 ms 10280 KB Output is correct
14 Correct 4 ms 10280 KB Output is correct
15 Correct 4 ms 10280 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14884 KB Output is correct
2 Correct 27 ms 14784 KB Output is correct
3 Correct 22 ms 14788 KB Output is correct
4 Correct 15 ms 12884 KB Output is correct
5 Correct 15 ms 13948 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 15 ms 13384 KB Output is correct
8 Correct 15 ms 13380 KB Output is correct
9 Correct 15 ms 13372 KB Output is correct
10 Correct 13 ms 12864 KB Output is correct
11 Correct 13 ms 12904 KB Output is correct
12 Correct 13 ms 12848 KB Output is correct
13 Correct 13 ms 12856 KB Output is correct
14 Correct 15 ms 12820 KB Output is correct
15 Correct 13 ms 12872 KB Output is correct
16 Correct 15 ms 12864 KB Output is correct
17 Correct 15 ms 12864 KB Output is correct
18 Correct 18 ms 12872 KB Output is correct
19 Correct 15 ms 12860 KB Output is correct
20 Correct 11 ms 13884 KB Output is correct
21 Correct 14 ms 13628 KB Output is correct
22 Correct 15 ms 13380 KB Output is correct
23 Correct 15 ms 13380 KB Output is correct
24 Correct 18 ms 13392 KB Output is correct
25 Correct 15 ms 13376 KB Output is correct
26 Correct 15 ms 13352 KB Output is correct
27 Correct 15 ms 13644 KB Output is correct
28 Correct 15 ms 13320 KB Output is correct
29 Correct 13 ms 13360 KB Output is correct
30 Correct 22 ms 13272 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14896 KB Output is correct
2 Correct 22 ms 14892 KB Output is correct
3 Correct 20 ms 14764 KB Output is correct
4 Correct 15 ms 12856 KB Output is correct
5 Correct 15 ms 14412 KB Output is correct
6 Correct 15 ms 13392 KB Output is correct
7 Correct 15 ms 13388 KB Output is correct
8 Correct 15 ms 13376 KB Output is correct
9 Correct 15 ms 13492 KB Output is correct
10 Correct 14 ms 12872 KB Output is correct
11 Correct 13 ms 13048 KB Output is correct
12 Correct 13 ms 12840 KB Output is correct
13 Correct 13 ms 12840 KB Output is correct
14 Correct 20 ms 13104 KB Output is correct
15 Correct 20 ms 12888 KB Output is correct
16 Correct 15 ms 12864 KB Output is correct
17 Correct 14 ms 12868 KB Output is correct
18 Correct 15 ms 12872 KB Output is correct
19 Correct 14 ms 12872 KB Output is correct
20 Correct 12 ms 13900 KB Output is correct
21 Correct 11 ms 13640 KB Output is correct
22 Correct 15 ms 13452 KB Output is correct
23 Correct 20 ms 13524 KB Output is correct
24 Correct 15 ms 13376 KB Output is correct
25 Correct 17 ms 13376 KB Output is correct
26 Correct 17 ms 13360 KB Output is correct
27 Correct 19 ms 13620 KB Output is correct
28 Correct 18 ms 13408 KB Output is correct
29 Correct 15 ms 13276 KB Output is correct
30 Correct 16 ms 13256 KB Output is correct
31 Correct 5 ms 10436 KB Output is correct
32 Correct 4 ms 10448 KB Output is correct
33 Correct 5 ms 10544 KB Output is correct
34 Correct 7 ms 10700 KB Output is correct
35 Correct 5 ms 10264 KB Output is correct
36 Correct 4 ms 10280 KB Output is correct
37 Correct 4 ms 10280 KB Output is correct
38 Correct 4 ms 10280 KB Output is correct
39 Correct 6 ms 10280 KB Output is correct
40 Correct 6 ms 10476 KB Output is correct
41 Correct 4 ms 10264 KB Output is correct
42 Correct 5 ms 10396 KB Output is correct