| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1296956 | danglayloi1 | Amusement Park (JOI17_amusement_park) | C++20 | 0 ms | 0 KiB |
#include "Joi.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e4+5;
struct Jay
{
// void MessageBoard(int u, int v)
// {
// }
vector<int> adj[nx], ve[nx];
bitset<nx> ed[nx];
queue<int> f;
bool vis[nx], id[nx];
int par[nx], deg[nx];
void init(int n)
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
ve[i].clear();
ed[i].reset();
while(f.size()) f.pop();
vis[i]=0;
id[i]=0;
par[i]=0;
deg[i]=0;
}
}
int find(int u)
{
if(!par[u]) return u;
return par[u]=find(par[u]);
}
bool join(int u, int v)
{
u=find(u);
v=find(v);
if(u==v) return 0;
par[v]=u;
return 1;
}
void joi(int n, int m, int a[], int b[], ll x, int t)
{
for(int i = 0; i < m; i++)
{
if(join(a[i], b[i]))
{
ed[a[i]][b[i]]=ed[b[i]][a[i]]=1;
adj[a[i]].emplace_back(b[i]);
adj[b[i]].emplace_back(a[i]);
}
}
f.push(0);
while(f.size())
{
int u=f.front();
f.pop();
for(int v:adj[u])
{
if(ve[0].size()==60) break;
if(!vis[v])
{
ve[0].emplace_back(v);
vis[v]=1;
f.push(v);
}
}
}
for(int i = 0; i < 60; i++)
id[ve[0][i]]=i, ve[ve[0][i]]=ve[0];
while(f.size()) f.pop();
for(int i = 0; i < n; i++)
if(!vis[i])
f.push(i);
while(f.size())
{
int u=f.front();
f.pop();
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]++;
int nxt=-1;
for(int i = 0; i < 60; i++)
if(deg[ve[u][i]]==1 && ve[u][i]!=u)
nxt=i;
for(int v:adj[u])
{
if(!vis[v])
{
vis[v]=1;
f.push(v);
ve[v]=ve[u];
ve[v][nxt]=v;
id[v]=nxt;
}
}
}
for(int i = 0; i < n; i++)
MessageBoard(i, x>>id[i]&1);
}
} J;
void Joi(int n, int m, int a[], int b[], ll x, int t)
{
J.init(n);
J.joi(n, m, a, b, x, t);
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// }
#include "Ioi.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e4+5;
struct Ai
{
// int Move(int u)
// {
// }
vector<int> adj[nx], ve[nx];
bitset<nx> ed[nx];
queue<int> f;
bool vis[nx], id[nx], ok[nx];
int par[nx], deg[nx], res[60];
void init(int n)
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
ve[i].clear();
ed[i].reset();
while(f.size()) f.pop();
vis[i]=0;
id[i]=0;
par[i]=0;
deg[i]=0;
ok[i]=0;
}
}
int find(int u)
{
if(!par[u]) return u;
return par[u]=find(par[u]);
}
bool join(int u, int v)
{
u=find(u);
v=find(v);
if(u==v) return 0;
par[v]=u;
return 1;
}
void dfs(int u, int val)
{
res[id[u]]=val;
vis[u]=1;
for(int v:adj[u])
if(!vis[v] && ok[v])
dfs(v, Move(v)), Move(u);
}
void ioi(int n, int m, int a[], int b[], int p, int val, int t)
{
for(int i = 0; i < m; i++)
{
if(join(a[i], b[i]))
{
ed[a[i]][b[i]]=ed[b[i]][a[i]]=1;
adj[a[i]].emplace_back(b[i]);
adj[b[i]].emplace_back(a[i]);
}
}
f.push(0);
while(f.size())
{
int u=f.front();
f.pop();
for(int v:adj[u])
{
if(ve[0].size()==60) break;
if(!vis[v])
{
ve[0].emplace_back(v);
vis[v]=1;
f.push(v);
}
}
}
for(int i = 0; i < 60; i++)
id[ve[0][i]]=i, ve[ve[0][i]]=ve[0];
while(f.size()) f.pop();
for(int i = 0; i < n; i++)
if(!vis[i])
f.push(i);
while(f.size())
{
int u=f.front();
f.pop();
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]++;
int nxt=-1;
for(int i = 0; i < 60; i++)
if(deg[ve[u][i]]==1 && ve[u][i]!=u)
nxt=i;
for(int v:adj[u])
{
if(!vis[v])
{
vis[v]=1;
f.push(v);
ve[v]=ve[u];
ve[v][nxt]=v;
id[v]=nxt;
}
}
}
for(int u:ve[p]) ok[u]=1, vis[u]=0;
dfs(p, val);
}
} I;
void Ioi(int n, int m, int a[], int b[], int p, int val, int t)
{
I.init(n);
I.ioi(n, m, a, b, p, val, t);
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// }