| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1045139 | karthi222528 | 공장들 (JOI14_factories) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int bp(int a,int b,int p){
int ret = 1;
while(b>0){
if(b&1){
ret = (ret*a)%p;
}
a = (a*a)%p;
b /= 2;
}
return ret;
}
int inv(int a,int p){
return bp(a,p-2,p);
}
struct DSU{
int n;
vector<int> par,rank;
DSU(int n){
this->n = n;
par.resize(n+1,-1);
rank.resize(n+1,1);
}
int find_set(int i){
if(par[i]==-1){
return i;
}
par[i] = find_set(par[i]);
return par[i];
}
void union_set(int a,int b){
int p1 = find_set(a);
int p2 = find_set(b);
if(p1!=p2){
if(rank[p1]>=rank[p2]){
rank[p1] += rank[p2];
par[p2] = p1;
}else{
rank[p2] += rank[p1];
par[p1] = p2;
}
}
}
};
struct FenwickTree{
int n;
vector<int> bit;
FenwickTree(int n){
this->n = n;
bit.resize(n,0);
}
int sum(int r){
int ret = 0;
while(r>=0){
ret += bit[r];
r = (r&(r+1)) - 1;
}
return ret;
}
void add(int idx,int del){
while(idx<n){
bit[idx] += del;
idx = (idx|(idx+1));
}
}
void add(int l,int r,int del){
if(l<=r){
add(l,del);
add(r+1,-del);
}
}
};
struct Trie{
int cnt,n;
vector<vector<int>> trie;
vector<bool> end;
Trie(int n){
this->n = n;
cnt = 0;
trie.assign(n+1,vector<int> (26,-1));
end.assign(n+1,false);
}
void insert(string &s){
int it = 0;
for(auto c: s){
if(trie[it][c-'a']==-1){
trie[it][c-'a'] = ++cnt;
}
it = trie[it][c-'a'];
}
end[it] = true;
return;
}
};
vector<int> sorted_cyclic_shifts(string &s){
int n = s.size();
int alpha = 128;
int alp = max(n,alpha);
vector<int> p(n),c(n),cnt(alp,0);
for(int i = 0;i<n;i++){
cnt[s[i]]++;
}
for(int i = 1;i<alpha;i++){
cnt[i] += cnt[i-1];
}
for(int i = 0;i<n;i++){
p[--cnt[s[i]]] = i;
}
c[p[0]] = 0;
int classes = 1;
for(int i = 1;i<n;i++){
if(s[p[i]] != s[p[i-1]]){
classes++;
}
c[p[i]] = classes - 1;
}
vector<int> pn(n),cn(n);
int len = 1;
for(int it = 0;len<n;it++){
for(int i = 0;i<n;i++){
pn[i] = (p[i] - len + n)%n;
}
fill(cnt.begin(),cnt.begin() + classes,0);
for(int i = 0;i<n;i++){
cnt[c[pn[i]]]++;
}
for(int i = 1;i<classes;i++){
cnt[i] += cnt[i-1];
}
for(int i = n-1;i>=0;i--){
p[--cnt[c[pn[i]]]] = pn[i];
}
cn[p[0]] = 0;
classes = 1;
for(int i = 1;i<n;i++){
pair<int,int> cur = {c[p[i]],c[(p[i] + len)%n]};
pair<int,int> prev = {c[p[i-1]],c[(p[i-1] + len)%n]};
if(cur!=prev){
classes++;
}
cn[p[i]] = classes - 1;
}
swap(c,cn);
len *= 2;
}
return p;
}
vector<int> suffix_array(string s){
vector<int> sorted_shifts = sorted_cyclic_shifts(s);
return sorted_shifts;
}
int hash_val(string s){
int n = s.length();
int p = 31;
int mod = 1500450271LL;
int ret = 0;
for(int i = 0;i<n;i++){
ret +=((s[i] - 'a')*bp(p,i,mod))%mod;
ret %= mod;
}
return ret;
}
struct segTree{
int n;
int inf = 1e18;
vector<pair<int,int>> st;
void init(int n){
this->n = n;
st.resize(4*n,{-1,inf});
}
pair<int,int> merge_pair(pair<int,int> &p1,pair<int,int> &p2){
if(p1.second<p2.second){
return p1;
}else{
if(p1.second>p2.second){
return p2;
}
if(p1.first<p2.first){
return p1;
}
return p2;
}
}
void build(int node,int s,int e,vector<pair<int,int>> &v){
if(s==e){
st[node] = v[s];
return;
}
int lc = 2*node + 1;
int rc = lc + 1;
int mid = s + (e-s)/2;
build(lc,s,mid,v);
build(rc,mid+1,e,v);
st[node] = merge_pair(st[lc],st[rc]);
return;
}
pair<int,int> query_min(int node,int s,int e,int l,int r){
if(e<l||s>r){
return {-1,inf};
}
if(s>=l&&e<=r){
return st[node];
}
int lc = 2*node + 1;
int rc = lc + 1;
int mid = s + (e-s)/2;
pair<int,int> le = query_min(lc,s,mid,l,r);
pair<int,int> ri = query_min(rc,mid+1,e,l,r);
return merge_pair(le,ri);
}
};
struct lca_tree{
int n;
int id = 0;
vector<vector<int>> adj;
map<pair<int,int>,int> wei;
vector<pair<int,int>> dfs_arr;
vector<int> dep,pos,rdep;
segTree seg;
void init(int n,vector<vector<int>> &tree,map<pair<int,int>,int> &weight){
this->n = n;
this->adj = tree;
this->wei = weight;
dep.resize(n+1,0);
rdep.resize(n+1,0);
pos.resize(n+1,1e15);
dfs(0,-1);
seg.init(2*n - 1);
seg.build(0,0,2*n - 2,dfs_arr);
pos_assign();
}
void dfs(int u,int p){
dfs_arr.push_back({u,dep[u]});
for(auto c: adj[u]){
if(c!=p){
dep[c] = dep[u] + 1;
rdep[c] = rdep[u] + wei[{u,c}];
dfs(c,u);
dfs_arr.push_back({u,dep[u]});
}
}
return;
}
void pos_assign(){
for(int i = 0;i<2*n - 1;i++){
pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
}
}
int lca(int u,int v){
int l = min(pos[u],pos[v]);
int r = max(pos[u],pos[v]);
pair<int,int> ret = seg.query_min(0,0,2*n - 2,l,r);
return ret.first;
}
int dist(int u,int v){
int lca_cur = lca(u,v);
return dep[u] + dep[v] - 2*dep[lca_cur];
}
int len(int u,int v){
int lca_cur = lca(u,v);
return rdep[u] + rdep[v] - 2*rdep[lca_cur];
}
};
struct centroid_decomposition{
vector<vector<int>> adj;
vector<bool> removed;
vector<int> sub,par;
int n;
void init(int n,vector<vector<int>> &tree){
this->n = n;
this->adj = tree;
removed.resize(n+1,false);
sub.resize(n+1,1);
par.resize(n+1,-1);
build(0,-1);
}
void build(int u,int p){
int sz = dfs(u,p);
int cent = centroid(u,p,sz);
removed[cent] = true;
//cout<<cent<<" ";
par[cent] = p;
for(auto c: adj[cent]){
if(!removed[c]){
build(c,cent);
}
}
return;
}
int dfs(int u,int p){
for(auto c: adj[u]){
if(c!=p&&!removed[c]){
sub[u] += dfs(c,u);
}
}
return sub[u];
}
int centroid(int u,int p,int sz){
for(auto c: adj[u]){
if(c!=p&&!removed[c]){
if(sub[c]>sz/2){
return centroid(c,u,sz);
}
}
}
return u;
}
};
lca_tree lct;
centroid_decomposition cd;
vector<int> ans;
void Init(int n,int u[],int v[],int l[]){
vector<vector<int>> adj(n+1);
map<pair<int,int>,int> wei;
for(int i = 0;i<n-1;i++){
wei[{u[i],v[i]}] = l[i];
wei[{v[i],u[i]}] = l[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
lct.init(n,adj,wei);
cd.init(n,adj);
ans.resize(n,1e15);
}
int Query(int s,int c1[],int t,int c2[]){
for(int i = 0;i<s;i++){
int node = c1[i];
while(node!=-1){
ans[node] = min(ans[node],lct.len(c1[i],node));
node = cd.par[node];
}
}
int fans = 1e15;
for(int i = 0;i<t;i++){
int node = c2[i];
while(node!=-1){
fans = min(fans,lct.len(c2[i],node) + ans[node]);
node = cd.par[node];
}
}
for(int i = 0;i<s;i++){
int node = c1[i];
while(node!=-1){
ans[node] = 1e15;
node = cd.par[node];
}
}
return fans;
}