제출 #1194908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194908		vnedu	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	134 ms	7752 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e4 + 10;
const int mb = 60;
const int root=1;
static vector<ii> edge[N];
static int n,m,mess[N];
static vector<int> adj[N];
static queue<int> q;

static struct Dsu
{
    int n,par[N];
    Dsu() {}
    void init(int _n)
    {
        n=_n;
        for(int i=0;i<n;++i) par[i]=i;
    }
    int get(int x)
    {
        if(x==par[x]) return x;
        return par[x]=get(par[x]);
    }
    bool unite(int x, int y)
    {
        int s=get(x),t=get(y);
        if(s==t) return 0;
        par[s]=t;
        return 1;
    }
} dsu;
static void dfs(int u, int pa)
{
    vector<ii> &owner=edge[pa];
    vector<ii> &dog=edge[u];
    int leaf,cmPos;
    for(int tri=0;tri<mb-1;++tri) for(int ok=0;ok<2;++ok)
    {
        int ver=(ok==0?owner[tri].fi:owner[tri].se);
        int cnt=0;
        for(int i=0;i<mb-1;++i) cnt+=(owner[i].fi==ver)+(owner[i].se==ver);
        if(cnt==1 && ver!=pa)
        {
            leaf=ver;
            cmPos=tri;
        }
    }
    mess[u]=mess[leaf];
    for(int tri=0;tri<mb-1;++tri) if(tri!=cmPos)
    {
        dog.pb(owner[tri]);
    }
    dog.pb({pa,u});

    for(int v : adj[u]) if(v!=pa) dfs(v,u);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
    n=N;
    m=M;
    dsu.init(n);
    for(int i=0;i<m;++i)
    {
        int u=A[i],v=B[i];
        if(dsu.unite(u,v))
        {
            adj[u].pb(v);
            adj[v].pb(u);
        }
    }
    memset(mess,-1,sizeof(mess));
    q.push(root);
    int tg=0;
    mess[root]=tg++;
    vector<ii> cur;
    while(tg<mb)
    {
        int u=q.front(); q.pop();
        for(int v : adj[u]) if(mess[v]==-1 && tg<mb)
        {
            cur.pb({u,v});
            q.push(v);
            mess[v]=tg++;
        }
    }
    for(int i=0;i<n;++i) if(mess[i]!=-1) edge[i]=cur;
    for(int i=0;i<n;++i) if(mess[i]!=-1)
    {
        for(int v : adj[i]) if(mess[v]==-1) dfs(v,i);
    }
    for(int i=0;i<n;++i) MessageBoard(i,(X>>mess[i])&1);
}

//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

////    int testcase=1;
//    cin>>testcase;

//    while (testcase--)
//        solve();

//    return 0;
//}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e4 + 10;
const int mb = 60;
const int root=1;
static vector<ii> edge[N];
static int n,m,mess[N];
static vector<int> adj[N];
static queue<int> q;

static struct Dsu
{
    int n,par[N];
    Dsu() {}
    void init(int _n)
    {
        n=_n;
        for(int i=0;i<n;++i) par[i]=i;
    }
    int get(int x)
    {
        if(x==par[x]) return x;
        return par[x]=get(par[x]);
    }
    bool unite(int x, int y)
    {
        int s=get(x),t=get(y);
        if(s==t) return 0;
        par[s]=t;
        return 1;
    }
} dsu;
static void dfs(int u, int pa)
{
    vector<ii> &owner=edge[pa];
    vector<ii> &dog=edge[u];
    int leaf=1,cmPos=-1;
    for(int tri=0;tri<mb-1;++tri) for(int ok=0;ok<2;++ok)
    {
        int ver=(ok==0?owner[tri].fi:owner[tri].se);
        int cnt=0;
        for(int i=0;i<mb-1;++i) cnt+=(owner[i].fi==ver)+(owner[i].se==ver);
        if(cnt==1 && ver!=pa)
        {
            leaf=ver;
            cmPos=tri;
        }
    }
    mess[u]=mess[leaf];
    for(int tri=0;tri<mb-1;++tri) if(tri!=cmPos)
    {
        dog.pb(owner[tri]);
    }
    dog.pb({pa,u});

    for(int v : adj[u]) if(v!=pa) dfs(v,u);
}
static ll ans=0;
static void trace(int u, int pa)
{
    for(int v : adj[u]) if(v!=pa)
    {
        ans|=(1LL<<mess[v])*Move(v);
        trace(v,u);
        ans|=(1LL<<mess[u])*Move(u);
    }
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    n=N;
    m=M;
    dsu.init(n);
    for(int i=0;i<m;++i)
    {
        int u=A[i],v=B[i];
        if(dsu.unite(u,v))
        {
            adj[u].pb(v);
            adj[v].pb(u);
        }
    }
    memset(mess,-1,sizeof(mess));
    q.push(root);
    int tg=0;
    mess[root]=tg++;
    vector<ii> cur;
    while(tg<mb)
    {
        int u=q.front(); q.pop();
        for(int v : adj[u]) if(mess[v]==-1 && tg<mb)
        {
            cur.pb({u,v});
            q.push(v);
            mess[v]=tg++;
        }
    }
    for(int i=0;i<n;++i) if(mess[i]!=-1) edge[i]=cur;
    for(int i=0;i<n;++i) if(mess[i]!=-1)
    {
        for(int v : adj[i]) if(mess[v]==-1) dfs(v,i);
    }
    for(int i=0;i<n;++i) vector<int>().swap(adj[i]);
    for(ii cm : edge[P])
    {
        adj[cm.fi].pb(cm.se);
        adj[cm.se].pb(cm.fi);
    }
    trace(P,-1);
    return ans;
}

//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

//    int testcase=1;
//    cin>>testcase;

//    while (testcase--)
//        solve();

//    return 0;
//}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17