Submission #1059508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059508		12345678	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	104 ms	78564 KiB

Joi

#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();
}

Ioi

#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 (stderr)

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17