oj.uz

Submission #1059508

# Submission time Handle Problem Language Result Execution time Memory
1059508 2024-08-15T04:13:49 Z 12345678 Amusement Park (JOI17_amusement_park) C++17
100 / 100
 104 ms 78564 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e4+5, mx=2e4+5, kx=60;

struct joi
{
    int n, m, a[mx], b[mx], vl[kx], dsu[nx], res[nx], f, idx, vs[nx];
    ll x;
    vector<int> d[nx], fgroup;
    vector<pair<int, int>> edg;
    queue<pair<int, int>> q;
    struct subgraph
    {
        int node[kx];
        vector<int> g[kx];
    } dp[nx];
    int find(int x)
    {
        if (dsu[x]==x) return x;
        return dsu[x]=find(dsu[x]);
    }
    void dfsfill(int u, int p)
    {
        vs[u]=1;
        res[u]=idx++;
        fgroup.push_back(u);
        if (u!=p) edg.push_back({p, u});
        for (auto v:d[u])
        {
            if (v==p) continue;
            if (idx==kx) q.push({v, u}), vs[v]=1;
            else dfsfill(v, u);
        }
    }
    void build()
    {
        for (int i=0; i<kx; i++) vl[i]=x%2, x/=2;
        for (int i=0; i<n; i++) dsu[i]=i;
        for (int i=0; i<m; i++) if (find(a[i])!=find(b[i])) dsu[find(a[i])]=find(b[i]), d[a[i]].push_back(b[i]), d[b[i]].push_back(a[i]);
        dfsfill(0, 0);
        for (auto x:fgroup) for (auto e:edg) dp[x].g[res[e.first]].push_back(res[e.second]), dp[x].g[res[e.second]].push_back(res[e.first]);
        for (auto x:fgroup) for (auto y:fgroup) dp[x].node[res[y]]=y;
        while (!q.empty())
        {
            auto [u, p]=q.front();
            q.pop();
            int del, ff=0;
            for (int i=0; i<kx; i++) dp[u].node[i]=dp[p].node[i];
            for (int i=0; i<kx; i++) if (dp[p].g[i].size()==1&&i!=res[p]) del=i;
            dp[u].node[del]=u;
            dp[u].g[del].push_back(res[p]);
            dp[u].g[res[p]].push_back(del);
            res[u]=del;
            for (int i=0; i<kx; i++) for (auto j:dp[p].g[i]) if (j!=del&&i!=del) dp[u].g[i].push_back(j);
            int szsm=0;
            for (int i=0; i<kx;i ++) szsm+=dp[u].g[i].size();
            for (auto v:d[u]) if (!vs[v]) q.push({v, u}), vs[v]=1;
        }
        for (int i=0; i<n; i++) MessageBoard(i, vl[res[i]]);
    }
} J;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    J.n=N, J.m=M;
    for (int i=0; i<M; i++) J.a[i]=A[i], J.b[i]=B[i];
    J.x=X;
    J.build();
}

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

using namespace std;

#define ll long long

const int nxx=1e4+5, mxx=2e4+5, kxx=60;

struct ioi
{
    int n, m, a[mxx], b[mxx], vl[kxx], dsu[nxx], res[nxx], f, idx, vs[nxx], st;
    ll x, ans, pw[kxx];
    vector<int> d[nxx], fgroup;
    vector<pair<int, int>> edg;
    queue<pair<int, int>> q;
    struct subgraph
    {
        int node[kxx];
        vector<int> g[kxx];
    } dp[nxx];
    int find(int x)
    {
        if (dsu[x]==x) return x;
        return dsu[x]=find(dsu[x]);
    }
    void dfsfill(int u, int p)
    {
        vs[u]=1;
        res[u]=idx++;
        fgroup.push_back(u);
        if (u!=p) edg.push_back({p, u});
        for (auto v:d[u])
        {
            if (v==p) continue;
            if (idx==kxx) q.push({v, u}), vs[v]=1;
            else dfsfill(v, u);
        }
    }
    void build()
    {
        pw[0]=1;
        for (int i=1; i<kxx; i++) pw[i]=pw[i-1]*2;
        for (int i=0; i<n; i++) dsu[i]=i;
        for (int i=0; i<m; i++) if (find(a[i])!=find(b[i])) dsu[find(a[i])]=find(b[i]), d[a[i]].push_back(b[i]), d[b[i]].push_back(a[i]);
        dfsfill(0, 0);
        for (auto x:fgroup) for (auto e:edg) dp[x].g[res[e.first]].push_back(res[e.second]), dp[x].g[res[e.second]].push_back(res[e.first]);
        //for (auto e:edg) if (e.first==0) cout<<"edge "<<e.first<<' '<<e.second<<'\n';
        for (auto x:fgroup) for (auto y:fgroup) dp[x].node[res[y]]=y;
        while (!q.empty())
        {
            auto [u, p]=q.front();
            q.pop();
            int del, ff=0;
            for (int i=0; i<kxx; i++) dp[u].node[i]=dp[p].node[i];
            for (int i=0; i<kxx; i++) if (dp[p].g[i].size()==1&&i!=res[p]) del=i;
            dp[u].node[del]=u;
            dp[u].g[del].push_back(res[p]);
            dp[u].g[res[p]].push_back(del);
            res[u]=del;
            for (int i=0; i<kxx; i++) for (auto j:dp[p].g[i]) if (j!=del&&i!=del) dp[u].g[i].push_back(j);
            int szsm=0;
            for (int i=0; i<kxx;i ++) szsm+=dp[u].g[i].size();
            //cout<<"sz "<<u<<' '<<(szsm/2)<<'\n';
            for (auto v:d[u]) if (!vs[v]) q.push({v, u}), vs[v]=1;
        }
    }
    void dfssolve(int u, int p, int rt)
    {
        for (auto v:dp[rt].g[u]) if (v!=p) vl[v]=Move(dp[rt].node[v]), dfssolve(v, u, rt);
        if (p!=u) vl[p]=Move(dp[rt].node[p]);
    }
    ll solve()
    {
        int stcolor;
        for (int i=0; i<kxx; i++) if (dp[st].node[i]==st) stcolor=i;
        dfssolve(stcolor, stcolor, st);
        for (int i=0; i<kxx; i++) ans+=vl[i]*pw[i];
        return ans;
    }
} I;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    I.n=N, I.m=M;
    for (int i=0; i<M; i++) I.a[i]=A[i], I.b[i]=B[i];
    I.st=P;
    I.build();
    return I.solve();
}

Compilation message

Joi.cpp: In member function 'void joi::build()':
Joi.cpp:52:22: warning: unused variable 'ff' [-Wunused-variable]
   52 |             int del, ff=0;
      |                      ^~

Ioi.cpp: In member function 'void ioi::build()':
Ioi.cpp:54:22: warning: unused variable 'ff' [-Wunused-variable]
   54 |             int del, ff=0;
      |                      ^~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:70:80: warning: 'stcolor' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |         for (auto v:dp[rt].g[u]) if (v!=p) vl[v]=Move(dp[rt].node[v]), dfssolve(v, u, rt);
      |                                                                        ~~~~~~~~^~~~~~~~~~
Ioi.cpp:75:13: note: 'stcolor' was declared here
   75 |         int stcolor;
      |             ^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34576 KB Output is correct
2 Correct 6 ms 35100 KB Output is correct
3 Correct 7 ms 35612 KB Output is correct
4 Correct 6 ms 34592 KB Output is correct
5 Correct 5 ms 34592 KB Output is correct
6 Correct 6 ms 35104 KB Output is correct
7 Correct 7 ms 35392 KB Output is correct
8 Correct 7 ms 35700 KB Output is correct
9 Correct 7 ms 35612 KB Output is correct
10 Correct 6 ms 35100 KB Output is correct
11 Correct 7 ms 35180 KB Output is correct
12 Correct 5 ms 34584 KB Output is correct
13 Correct 11 ms 35608 KB Output is correct
14 Correct 7 ms 35576 KB Output is correct
15 Correct 7 ms 35640 KB Output is correct
16 Correct 7 ms 35620 KB Output is correct
17 Correct 7 ms 35620 KB Output is correct
18 Correct 7 ms 35616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 74428 KB Output is correct
2 Correct 91 ms 74428 KB Output is correct
3 Correct 89 ms 74412 KB Output is correct
4 Correct 84 ms 74204 KB Output is correct
5 Correct 91 ms 73608 KB Output is correct
6 Correct 86 ms 73424 KB Output is correct
7 Correct 87 ms 73792 KB Output is correct
8 Correct 86 ms 73624 KB Output is correct
9 Correct 87 ms 73812 KB Output is correct
10 Correct 93 ms 78560 KB Output is correct
11 Correct 84 ms 78556 KB Output is correct
12 Correct 79 ms 70000 KB Output is correct
13 Correct 86 ms 69868 KB Output is correct
14 Correct 81 ms 71880 KB Output is correct
15 Correct 84 ms 74004 KB Output is correct
16 Correct 92 ms 74040 KB Output is correct
17 Correct 87 ms 74976 KB Output is correct
18 Correct 84 ms 75596 KB Output is correct
19 Correct 84 ms 74452 KB Output is correct
20 Correct 76 ms 73624 KB Output is correct
21 Correct 75 ms 72916 KB Output is correct
22 Correct 84 ms 73432 KB Output is correct
23 Correct 84 ms 73564 KB Output is correct
24 Correct 83 ms 73440 KB Output is correct
25 Correct 83 ms 73440 KB Output is correct
26 Correct 84 ms 73596 KB Output is correct
27 Correct 83 ms 73428 KB Output is correct
28 Correct 86 ms 73432 KB Output is correct
29 Correct 77 ms 69820 KB Output is correct
30 Correct 81 ms 71624 KB Output is correct
31 Correct 9 ms 35092 KB Output is correct
32 Correct 6 ms 35104 KB Output is correct
33 Correct 7 ms 35732 KB Output is correct
34 Correct 6 ms 35108 KB Output is correct
35 Correct 6 ms 34592 KB Output is correct
36 Correct 5 ms 34592 KB Output is correct
37 Correct 5 ms 34580 KB Output is correct
38 Correct 6 ms 34580 KB Output is correct
39 Correct 5 ms 34592 KB Output is correct
40 Correct 6 ms 34592 KB Output is correct
41 Correct 5 ms 34592 KB Output is correct
42 Correct 5 ms 34592 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34596 KB Output is correct
2 Correct 6 ms 34592 KB Output is correct
3 Correct 7 ms 34584 KB Output is correct
4 Correct 17 ms 40692 KB Output is correct
5 Correct 16 ms 40772 KB Output is correct
6 Correct 18 ms 40812 KB Output is correct
7 Correct 16 ms 40776 KB Output is correct
8 Correct 16 ms 40680 KB Output is correct
9 Correct 75 ms 73260 KB Output is correct
10 Correct 75 ms 73136 KB Output is correct
11 Correct 75 ms 73024 KB Output is correct
12 Correct 5 ms 35096 KB Output is correct
13 Correct 6 ms 34592 KB Output is correct
14 Correct 5 ms 34584 KB Output is correct
15 Correct 6 ms 34592 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 74572 KB Output is correct
2 Correct 93 ms 74552 KB Output is correct
3 Correct 92 ms 74428 KB Output is correct
4 Correct 86 ms 74036 KB Output is correct
5 Correct 87 ms 73636 KB Output is correct
6 Correct 83 ms 73524 KB Output is correct
7 Correct 96 ms 73788 KB Output is correct
8 Correct 86 ms 73448 KB Output is correct
9 Correct 83 ms 73460 KB Output is correct
10 Correct 88 ms 78424 KB Output is correct
11 Correct 89 ms 78552 KB Output is correct
12 Correct 90 ms 70088 KB Output is correct
13 Correct 78 ms 69860 KB Output is correct
14 Correct 91 ms 71740 KB Output is correct
15 Correct 87 ms 73940 KB Output is correct
16 Correct 86 ms 73912 KB Output is correct
17 Correct 89 ms 74972 KB Output is correct
18 Correct 83 ms 74976 KB Output is correct
19 Correct 92 ms 74060 KB Output is correct
20 Correct 95 ms 73428 KB Output is correct
21 Correct 77 ms 72916 KB Output is correct
22 Correct 83 ms 73528 KB Output is correct
23 Correct 95 ms 73516 KB Output is correct
24 Correct 82 ms 73428 KB Output is correct
25 Correct 86 ms 73480 KB Output is correct
26 Correct 82 ms 73492 KB Output is correct
27 Correct 84 ms 73632 KB Output is correct
28 Correct 89 ms 73444 KB Output is correct
29 Correct 80 ms 69832 KB Output is correct
30 Correct 95 ms 71644 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 74656 KB Output is correct
2 Correct 87 ms 74440 KB Output is correct
3 Correct 104 ms 74668 KB Output is correct
4 Correct 88 ms 74292 KB Output is correct
5 Correct 89 ms 73428 KB Output is correct
6 Correct 83 ms 73560 KB Output is correct
7 Correct 86 ms 73616 KB Output is correct
8 Correct 90 ms 73684 KB Output is correct
9 Correct 84 ms 73428 KB Output is correct
10 Correct 90 ms 78556 KB Output is correct
11 Correct 89 ms 78564 KB Output is correct
12 Correct 77 ms 69916 KB Output is correct
13 Correct 77 ms 69820 KB Output is correct
14 Correct 81 ms 71836 KB Output is correct
15 Correct 94 ms 73940 KB Output is correct
16 Correct 86 ms 73940 KB Output is correct
17 Correct 88 ms 73940 KB Output is correct
18 Correct 87 ms 74196 KB Output is correct
19 Correct 90 ms 74472 KB Output is correct
20 Correct 77 ms 73876 KB Output is correct
21 Correct 75 ms 72932 KB Output is correct
22 Correct 84 ms 73460 KB Output is correct
23 Correct 83 ms 73476 KB Output is correct
24 Correct 83 ms 73440 KB Output is correct
25 Correct 84 ms 73520 KB Output is correct
26 Correct 83 ms 73464 KB Output is correct
27 Correct 86 ms 73428 KB Output is correct
28 Correct 84 ms 73428 KB Output is correct
29 Correct 83 ms 69832 KB Output is correct
30 Correct 80 ms 71636 KB Output is correct
31 Correct 6 ms 35104 KB Output is correct
32 Correct 6 ms 35096 KB Output is correct
33 Correct 6 ms 35728 KB Output is correct
34 Correct 6 ms 35100 KB Output is correct
35 Correct 6 ms 34592 KB Output is correct
36 Correct 6 ms 34596 KB Output is correct
37 Correct 5 ms 35096 KB Output is correct
38 Correct 5 ms 34584 KB Output is correct
39 Correct 5 ms 34592 KB Output is correct
40 Correct 5 ms 34580 KB Output is correct
41 Correct 6 ms 34588 KB Output is correct
42 Correct 5 ms 34588 KB Output is correct