API tools faq
paste
Advertisement
Wazedrifat

rafin.cpp

Wazedrifat
Feb 19th, 2020
203
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 47.43 KB | None | 0 0
raw download clone embed print report
  1. suffix array: struct suff { int index; int Rank[2]; bool operator <(const suff &o)const{ return (Rank[0]<o.Rank[0])||(Rank[0]==o.Rank[0]&&Rank[1]<o.Rank[1]); } }; suff suffix[mx];ll lcp[mx];suff tmp[mx];int n,fr[mx];string s;int ind[mx],sa[mx]; char str[mx];int R[mx]; void Sort(int u) { int maxi=max(n,256); memset(fr,0,sizeof(fr)); for(int i=0;i<n;i++)fr[suffix[i].Rank[u]+1]++; ll sum=0; for(int i=0;i<=maxi;i++) { ll prev=fr[i]; fr[i]=sum; sum+=prev; } for(int i=0;i<n;i++) { tmp[fr[suffix[i].Rank[u]+1]]=suffix[i]; fr[suffix[i].Rank[u]+1]++; } for(int i=0;i<n;i++)suffix[i]=tmp[i]; } void SA() { int mini=10000; for(int i=0;i<n;i++) { mini=min(mini,(int)s[i]); } for(int i=0;i<n;i++) { suffix[i].index=i; suffix[i].Rank[0]=s[i]-mini; if(i+1<n)suffix[i].Rank[1]=s[i+1]-mini; else suffix[i].Rank[1]=-1; } Sort(1);Sort(0); for(int k=4;k<2*n;k=k*2){ int r=0; ind[suffix[0].index]=0; int prev=suffix[0].Rank[0]; suffix[0].Rank[0]=r; for(int i=1;i<n;i++){ if(prev==suffix[i].Rank[0]&&suffix[i].Rank[1]==suffix[i-1].Rank[1]) { prev=suffix[i].Rank[0]; suffix[i].Rank[0]=r; } else{ prev=suffix[i].Rank[0]; suffix[i].Rank[0]=++r; } ind[suffix[i].index]=i; } for(int i=0;i<n;i++){ int next=suffix[i].index+k/2; if(next<n)suffix[i].Rank[1]=suffix[ind[next]].Rank[0]; else suffix[i].Rank[1]=-1; } Sort(1);Sort(0); } /*for(int i=0;i<n;i++)cout<<suffix[i].index<<endl;*/ } void kasai() { int k=0;ll gum=0; for(int i=0;i<n;i++)R[suffix[i].index]=i; for(int i=0;i<n;i++)sa[R[i]]=i; for(int i=0;i<n;i++) { if(R[i]==n-1) { k=0; continue; } int j=suffix[R[i]+1].index; while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++; lcp[R[i]]=k; if(k>0)k--; } } int main() { int t; scanf("%d",&t); while(t--){ scanf("%s",str); s=str; n=s.length(); SA(); kasai(); ll ans=0; /*for(int i=0;i<n-1;i++)cout<<lcp[i]<<endl;*/ ll maxi=0,save=-1;int mnt=1,save2=1; for(int i=0;i<n-1;i++) { if(lcp[i]>maxi) { maxi=lcp[i]; save=sa[i]; } } if(maxi==0)printf("No repetitions found!\n"); else { int cnt=save; for(int i=0;i<maxi;i++)printf("%c",s[cnt++]); for(int i=0;i<n;i++) { if(sa[i]==save) { while(lcp[i]==maxi) { save2++; i++; if(i==n-1)break; } break; } } printf(" %d\n",save2); } } return 0; }
  2.  
  3.  
  4.  
  5. Mobious Function: int miu[MAX],mark[MAX]; void mobius(int n){ for(int i=0;i<=n;i++) miu[i]=1; miu[0]=0; miu[1]=1; for(int i=2;i<=n;i++){ if(mark[i]) continue; miu[i]=-1; for(int j=i*2;j<=n;j+=i){ if(miu[j]!=0){ if(j%(i*i)==0) miu[j]=0; else miu[j]*=-1; mark[j]=1; } } } }
  6.  
  7.  
  8.  
  9.  
  10. CRT: /*A CRT solver which works even when moduli are not pairwise coprime 1. Add equations using addEquation() method 2. Call solve() to get {x, N} pair, where x is the unique solution modulo N. Assumptions: 1. LCM of all mods will fit into long long. */ class ChineseRemainderTheorem { typedef long long vlong; typedef pair<vlong,vlong> pll; /** CRT Equations stored as pairs of vector. See addEqation()*/ vector<pll> equations; public: void clear() { equations.clear(); } vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){ vlong x2, y2, x1, y1, x, y, r2, r1, q, r; x2 = 1; y2 = 0; x1 = 0; y1 = 1; for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) { q = r2 / r1; r = r2 % r1; x = x2 - (q * x1); y = y2 - (q * y1); } *X = x2; *Y = y2; return r2; } /** Add equation of the form x = r (mod m)*/ void addEquation( vlong r, vlong m ) { equations.push_back({r, m}); } pll solve() { if (equations.size() == 0) return {-1,-1}; /*/ No equations to solve*/ vlong a1 = equations[0].first; vlong m1 = equations[0].second; a1 %= m1; /** Initially x = a_0 (mod m_0)*/ /** Merge the solution with remaining equations */ for ( int i = 1; i < equations.size(); i++ ) { vlong a2 = equations[i].first; vlong m2 = equations[i].second; vlong g = __gcd(m1, m2); if ( a1 % g != a2 % g ) return {-1,-1}; /*/ Conflict in equations*/ /** Merge the two equations*/ vlong p, q; ext_gcd(m1/g, m2/g, &p, &q); vlong mod = m1 / g * m2; vlong x = ( (__int128)a1 * (m2/g) % mod *q % mod + (__int128)a2 * (m1/g) % mod * p % mod ) % mod; /** Merged equation*/ a1 = x; if ( a1 < 0 ) a1 += mod; m1 = mod; } return {a1, m1}; } };
  11.  
  12.  
  13.  
  14.  
  15. dp on tree: ll n,arr[MAX];vi v[MAX];ll choto[MAX],boro[MAX],ans; void dfs1(int s,int p = 0) { choto[s] = arr[s]; for(auto it : v[s]) { if(it==p)continue; dfs1(it,s); boro[s]+=choto[it]+boro[it]; choto[s]+=choto[it]; } } void dfs2(int s,int p = 0) { if(p) boro[s]=boro[p]+choto[p]-choto[s]-choto[s]; if(p) choto[s]=choto[p]; ans = max(ans,boro[s]); for(auto it : v[s]) { if(it==p)continue; dfs2(it,s); } } int main() { cin>>n; for(int i = 1;i<=n;i++)cin>>arr[i]; for(int i = 0;i<n-1;i++) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } dfs1(1); dfs2(1); cout<<ans; return 0; }
  16.  
  17.  
  18.  
  19.  
  20. Sprague Grundy Dividing Piles: int gr[MAX];int ans,f[MAX],root,pre[MAX]; void grundy(int n){ int y = 0; for(int i = 2;;i++){/* Number of ways of dividing */ if(i*(i-1)>=2*n)break; int x = n - (i*(i-1))/2; if(x%i)continue; x/=i; y = pre[x-1]^pre[x+i-1]; if(!y&&ans==-1&&n==root)ans = i;/*if xor of second step is zero that means 1st player will win because */ /* cout<<y<<endl;/* second player starts from 2nd step. that's why !y comes .*/ f[y] = n;/*keep tracking the grundy values*/ } int cc = 0; while(f[cc]==n)cc++;/*mex of all grundies is grundy for n*/ gr[n] = cc; pre[n] = cc; pre[n]^=pre[n-1]; } int main() { booster() /*/read("input.txt");*/ int n; cin>>n; root = n; ans = -1; for(int i = 3;i<=n;i++){ grundy(i); } if(gr[n])cout<<ans; else cout<<-1; return 0; }
  21.  
  22.  
  23.  
  24.  
  25. java bigint: package myFirst; import java.math.BigInteger; import java.math.RoundingMode; import java.math.BigDecimal; import java.util.*; public class mathfun { public static void main(String[] args) { /* TODO Auto-generated method stub*/ Scanner sc = new Scanner(System.in); BigInteger num = sc.nextBigInteger(); BigInteger num2 = sc.nextBigInteger(); BigInteger Add,Sub,Mul,Div,Mod; Add = num.add(num2); Sub = num.subtract(num2); Mul = num.multiply(num2); Div = num.divide(num2); Mod = num.mod(num2); System.out.println(Add + " "+ Sub + " " + Mul +" " +Div +" "+ Mod ); BigInteger sum = new BigInteger("0"); for(int i = 1;i<=10005;i++) { BigInteger x = new BigInteger(Integer.toString(i)); sum = sum.add(Add.mod(x)); } System.out.println(sum); if(sum.compareTo(new BigInteger("800"))>=0)System.out.println("YES"); if(sum.compareTo(Add)>=0)System.out.println("YES"); for(BigInteger i = BigInteger.ONE;i.compareTo(new BigInteger("10"))<=0;i = i.add(BigInteger.ONE)) { System.out.println(i); } sum = sum.gcd(Add); boolean tr; tr = sum.isProbablePrime(1); tr = new BigInteger("7").isProbablePrime(1); System.out.println(tr); BigDecimal b = new BigDecimal("100"); System.out.println(b.divide(new BigDecimal("3"),5,RoundingMode.CEILING)); System.out.println("Mod Pow = " + a.modPow(b, new BigInteger("10000009"))); /* returns a^b mod 10000009*/ System.out.println("Modulus Inverse = " + a.modInverse(b)); /* a^-1 mod b, this throws ArithmeticException - b ≤ 0, or 'a' BigInteger has no multiplicative inverse mod b (that is, this 'a' is not relatively prime to 'b'*/ System.out.println("GCD = " + a.gcd(b)); /* finds gcd, how cool is this?*/ System.out.println( a.isProbablePrime(15)? true: false ); /* checks if the number is probably prime or not , uses th Miller-Rabin primality test and with certainty of about 15 it is good enough to produce correct results.*/ System.out.println("Next prime after" + a + " is " + a.nextProbablePrime());/* Returns the first integer greater than a that is probably prime.*/ } }
  26.  
  27.  
  28.  
  29.  
  30. palindrome tree: ll tree[MAX][30],idx,link[MAX],len[MAX],t,pree[MAX][30],cnt;char s[MAX];ll occ[MAX];ll ans1[MAX],ans2[MAX];ll f[MAX],e[MAX]; void initialize() { len[1] = -1; len[2] = 0; link[1] = 1; link[2] = 1; t = idx = 2; mem(tree,0); mem(occ,0); } int extend(int p){ int save; while(s[p - len[t] - 1] != s[p]) t = link[t]; int x = link[t], c = s[p] - 'a'; while(s[p - len[x] - 1] != s[p]) x = link[x]; if(!tree[t][c]) { tree[t][c] = ++idx; save = idx; len[idx] = len[t] + 2; link[idx] = len[idx] == 1 ? 2 : tree[x][c]; } else { save = tree[t][c]; } t = tree[t][c]; return save; } int main() { scanf(" %s",s+1); initialize();int l = strlen(s+1); for(int i = 1;i<=l;i++){ int x = extend(i); f[i] = x; } for(int i = 3;i<=idx;i++){ occ[i]+=occ[link[i]] + 1; } for(int i = 1;i<=l;i++){ int x = f[i]; ans1[i] = occ[x]; } string s2 = s+1; reverse(all(s2)); for(int i = 1;i<=l;i++)s[i] = s2[i-1]; initialize(); for(int i = 1;i<=l;i++){ int x = extend(i); e[i] = x; } for(int i = 3;i<=idx;i++){ occ[i]+=occ[link[i]] + 1; } for(int i = 1;i<=l;i++){ ans2[l-i+1] = occ[e[i]]; } for(int i = l-1;i>=1;i--)ans2[i]+=ans2[i+1]; ull ans = 0; for(int i = 1;i<=l-1;i++){ ans+=(ans1[i] * ans2[i+1]); } cout<<ans<<endl; return 0; } int tree[MAX][30],idx,link[MAX],len[MAX],t,pree[MAX][30],cnt;char s[MAX];ll occ[MAX]; void initialize() { len[1] = -1; len[2] = 0; link[1] = 1; link[2] = 1; t = idx = 2; } void extend(int p){ while(s[p - len[t] - 1] != s[p]) t = link[t]; int x = link[t], c = s[p] - 'a'; while(s[p - len[x] - 1] != s[p]) x = link[x]; if(!tree[t][c]) { tree[t][c] = ++idx; occ[idx]++; len[idx] = len[t] + 2; link[idx] = len[idx] == 1 ? 2 : tree[x][c]; } else occ[tree[t][c]]++; t = tree[t][c]; } int main() { scanf(" %s",s+1); initialize();int l = strlen(s+1); for(int i = 1;i<=l;i++){ extend(i); } for(int i = idx;i>2;i--){ occ[link[i]]+=occ[i]; } ll ans = 0; for(int i = idx;i>2;i--)ans+=occ[i]; cout<<ans; return 0; }
  31.  
  32.  
  33.  
  34.  
  35. pollard-rho: i128 In( string s){ i128 x = 0; for(int i = 0;i<s.length();i++)x = x*10 + s[i] - 48; return x; } void out(i128 x){ vi v; while(x){ int y = x%10; x/=10; v.pb(y); } reverse(all(v)); for(auto it : v)printf("%d",it); } i128 mul(i128 a,i128 b,i128 m){ i128 ans = 0; while(b){ /*/cout<<a<<" "<<b<<" "<<m<<endl;*/ if(b&1)ans = (ans + a)%m; a = (a+a)%m; b>>=1; } return ans; } i128 power(i128 base,i128 p,i128 m){ /*/cout<<base<<" "<<p<<" "<<m<<endl;*/ if(p==0)return 1; if(p&1)return (base % m * power(base,p-1,m) % m)%m; else { i128 x = power(base,p/2,m)%m; return mul(x,x,m)%m; } } bool miller_rabin(i128 p,i128 d){ i128 a = rand() %(p-4) + 2; i128 x = power(a,d,p); if(x==1||x==p-1)return true; while(d!=p-1){ x = mul(x,x,p)%p; d = d*2; if(x==1)return false; if(x==p-1)return true; } return false; } bool isPrime(i128 n){ if(n<=1||n==4)return false; if(n<=3)return true; i128 d = n-1; while(d%2==0){ d/=2; } for(int i = 0;i<4;i++)if(!miller_rabin(n,d))return false; return true; } i128 GCD(i128 a,i128 b){ if(b==0)return a; return GCD(b,a%b); } i128 pollard_rho(i128 n){ i128 x = 2,xs = 2,Count ,Size = 2,factor = 1; i128 c = rand()%n+2; do { Count = Size; do{ x = (mul(x,x,n) + c)%n; i128 ab; if(xs>x)ab = xs - x; else ab = x - xs; factor = GCD(ab,n); }while(Count--&&factor==1); Size*=2; xs = x; }while(factor==1); if(factor==n){ do{ xs = (mul(xs,xs,n) + c)%n; i128 ab; if(xs>x)ab = xs - x; else ab = x - xs; factor = GCD(ab,n); }while(factor==1); } return factor; } vector<i128>fact; void FindFactors(i128 n){ queue<i128>q; q.push(n); while(!q.empty()){ i128 x = q.front(); q.pop(); i128 y = pollard_rho(x); if(isPrime(y))fact.pb(y); else{ q.push(y); } if(isPrime(x/y))fact.pb(x/y); else { if(x/y!=1&&x/y!=x)q.push(x/y); } } } int main() { while(1){ string s; char str[50]; scanf("%s",str); s = str; fact.clear(); if(s[0]=='0')return 0; i128 x = In(s); FindFactors(x); map<i128,int>m; for(auto it : fact)m[it]++; for(auto it : m){ out(it.ff); printf("^%d ",it.ss); } printf("\n"); } return 0; }
  36.  
  37.  
  38.  
  39.  
  40. dsu on tree: int n,big[MAX];vi v[MAX];char c[MAX]; int ans[MAX];int vis[MAX];vector<pii>ques[MAX]; int Sz[MAX],col[MAX][30];int cnt,maxi;vi v2;char str[MAX]; void dfs2(int s,int p){ Sz[s] = 1; for(auto it : v[s]){ if(it==p)continue; dfs2(it,s); Sz[s]+=Sz[it]; } } void add(int s,int p,int val,int depth){ col[depth][c[s]-96]+=val; for(auto it : v[s]){ if(p==it||big[it])continue; add(it,s,val,depth+1); } } void dfs(int s,int p,int keep,int depth){ int b = -1,mx = -1; for(auto it : v[s]){ if(Sz[it]>mx&&it!=p){ mx = Sz[it]; b = it; } } for(auto it : v[s]){ if(it!=b&&it!=p)dfs(it,s,0,depth+1); } if(b!=-1)dfs(b,s,1,depth+1),big[b] = 1; add(s,p,1,depth); for(auto it : ques[s]){ int jor = 0,bijor = 0; for(char ch = 'a';ch<='z';ch++){ if(col[it.ff][ch-96]&1)bijor++; else jor++; } if(bijor<=1)ans[it.ss] = 1; else ans[it.ss] = 0; } if(b!=-1)big[b] = 0; if(!keep)add(s,p,-1,depth),cnt=0,maxi=0; } int main() { scani(n); int q; scani(q); string st; for(int i = 0;i<n-1;i++){ int a; scani(a); v[a].pb(i+2); } scanf(" %s",str); st = str; for(int i = 0;i<n;i++)c[i+1] = st[i]; for(int i = 0;i<q;i++){ int a,b; scani2(a,b); ques[a].pb(pii(b,i+1)); } dfs2(1,0); dfs(1,0,1,1); for(int i = 1;i<=q;i++){ if(ans[i])puts("Yes"); else puts("No"); } return 0; }
  41.  
  42.  
  43.  
  44.  
  45. miller_rabin: i128 mul(i128 a,i128 b,i128 m){ i128 ans = 0; while(b){ if(b&1)ans = (ans + a)%m; a = (a+a)%m; b>>=1; } return ans; } i128 power(i128 base,i128 p,i128 m){ if(p==0)return 1; if(p&1)return (base % m * power(base,p-1,m) % m)%m; else { i128 x = power(base,p/2,m)%m; return mul(x,x,m)%m; } } bool miller_rabin(i128 p,i128 d){ i128 a = rand() %(p-4) + 2; i128 x = power(a,d,p); if(x==1||x==p-1)return true; while(d!=p-1){ x = mul(x,x,p)%p; d = d*2; if(x==1)return false; if(x==p-1)return true; } return false; } bool isPrime(i128 n){ if(n<=1||n==4)return false; if(n<=3)return true; i128 d = n-1; while(d%2==0){ d/=2; } for(int i = 0;i<4;i++)if(!miller_rabin(n,d))return false; return true; } int main() { int t; scani(t); while(t--){ ll x; scanf("%lld",&x); if(isPrime(x))puts("prime"); else puts("composite"); } }
  46.  
  47.  
  48.  
  49.  
  50. persistent seg tree: int arr[MAX]; struct node{ node *left,*right; int sum; node(){ sum = 0; left = right = NULL; } }*root[MAX]; node* Build(int b,int e){ if(b==e){ node *ret = new node(); ret->sum = arr[b]; return ret; } int mid = (b+e)>>1; node *ret = new node(); ret->left = Build(b,mid); ret->right = Build(mid+1,e); ret->sum = ret->left->sum + ret->right->sum; return ret; } node *update(node *ptr,int b,int e,int indx,int val){ if(b>indx||indx>e)return ptr; if(b==e){ node *ret = new node(); ret->sum = ptr->sum + val; return ret; } int mid = (b+e)>>1; node *ret = new node(); ret->left = update(ptr->left,b,mid,indx,val); ret->right = update(ptr->right,mid+1,e,indx,val); ret->sum = ret->left->sum + ret->right->sum; return ret; } int query(node *ptr,int b,int e,int l,int r){ if(b>r||l>e)return 0; if(b>=l&&e<=r)return ptr->sum; int mid = (b+e)>>1; return query(ptr->left,b,mid,l,r) + query(ptr->right,mid+1,e,l,r); } int main() { int n; cin>>n; for(int i = 1;i<=n;i++)cin>>arr[i]; root[0] = Build(1,n); int q; cin>>q; int ajinka = 1; while(q--){ int ch; cin>>ch; int idx; int a,b; cin>>idx>>a>>b; if(ch==1){ root[ajinka] = update(root[idx],1,n,a,b); ajinka++; } else cout<<query(root[idx],1,n,a,b)<<endl; } return 0; }
  51.  
  52.  
  53.  
  54.  
  55. min cost max flow: struct Treap{ /*/ hash = 96814*/ int len; const int ADD = 1000010; const int MAXVAL = 1000000010; tr1::unordered_map <long long, int> mp; /*/ Change to int if only int in treap*/ tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> T; Treap(){ len = 0; T.clear(), mp.clear(); } inline void clear(){ len = 0; T.clear(), mp.clear(); } inline void insert(long long x){ len++, x += MAXVAL; int c = mp[x]++; T.insert((x * ADD) + c); } inline void erase(long long x){ x += MAXVAL; int c = mp[x]; if (c){ c--, mp[x]--, len--; T.erase((x * ADD) + c); } } /*/ 1-based index, returns the K'th element in the treap, -1 if none exists*/ inline long long kth(int k){ if (k < 1 || k > len) return -1; auto it = T.find_by_order(--k); return ((*it) / ADD) - MAXVAL; } /*/ Count of value < x in treap*/ inline int count(long long x){ x += MAXVAL; int c = mp[--x]; return (T.order_of_key((x * ADD) + c)); } /*/ Number of elements in treap*/ inline int size(){ return len; } }; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;/*/*X.find_by_order();X.order_of_key();**/*/ template <class T> inline bool isLeap(T y) {return (y % 400 == 0) || (y % 100 ? y % 4 == 0 : false); } template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % (b))); } template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b)) * (b)); } template <class T> inline T BigMod(T Base,T power,T M=mod){if(power==0)return 1;if(power&1)return ((Base%M)*(BigMod(Base,power-1,M)%M))%M;else{T y=BigMod(Base,power/2,M)%M;return (y*y)%M;}} template <class T> inline T ModInv (T A,T M = mod){return BigMod(A,M-2,M);} int fx[] = {-1,+0,+1,+0,+1,+1,-1,-1,+0}; int fy[] = {+0,-1,+0,+1,+1,-1,+1,-1,+0}; int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int pt[MAX];vi v[MAX];string ptt[MAX];int ans,dtt[MAX],non[505][505],fl[505],pos1[505],pos2[505],cl[505]; const int N = 505*2; const ll INF=(ll)1<<60; struct Edge{ ll from,to,cap,flow,cost; Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost) {} }; namespace mcmf{ int n,m,s,t; vector<Edge> edges; vector<ll> G[N]; bool inq[N]; ll d[N],p[N],a[N]; /*/ N = Size of nodes in flow network*/ void init(int src,int sink,int node) { n=node; s= src; t = sink; edges.clear(); for(int i=0;i<=n;++i) G[i].clear(); } void addEdge(int from,int to,ll cap,ll cost) { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool spfa(ll &flow,ll& cost) { for(int i=0;i<=n;++i) d[i]=INF,inq[i]=0; queue<int> que; que.push(s); inq[s]=1;d[s]=0;p[s]=0;a[s]=INF; while(!que.empty()) { int x=que.front();que.pop(); inq[x]=0; for(int i=0;i<G[x].size();++i) { Edge &e=edges[G[x][i]]; if(e.cap>e.flow && d[e.to]>d[x]+e.cost) { d[e.to]=d[x]+e.cost; p[e.to]=G[x][i]; a[e.to]=min(a[x],e.cap-e.flow); if(!inq[e.to]) inq[e.to]=1,que.push(e.to); } } } if(d[t]==INF) return 0; flow+=a[t]; cost+=d[t]; /*/ multiply by d[t]*a[t] if per unit cost is given.*/ int u=t; while(u!=s) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return 1; } pll solve() { ll flow=0,cost=0; while(spfa(flow,cost)); return make_pair(cost,flow); } } int sor; int occ(string s,string ss,int indx) { int z[1005]; mem(z,0); int n = s.length(); int L = 0, R = 0; for (int i = 1; i < n; i++) { if (i > R) { L = R = i; while (R < n && s[R-L] == s[R]) R++; z[i] = R-L; R--; } else { int k = i-L; if (z[k] < R-i+1) z[i] = z[k]; else { L = i; while (R < n && s[R-L] == s[R]) R++; z[i] = R-L; R--; } } } int cnt = 0; for(int i = 0;i<n;i++) { if(z[i]==ss.length()) { mcmf::addEdge(i-ss.length()-1,i-1,1,-dtt[indx]); } } return cnt; } int main() { string s; int n; cin>>n>>s; int cnt = 0; for(int i = 0;i<n;i++) { pos1[i] = cnt++; pos2[i] = cnt++; } sor = cnt; mcmf::init(n+1,n+2,n+3); int m; cin>>m; for(int i = 0;i<m;i++) { cin>>ptt[i]>>dtt[i]; } int q; cin>>q; for(int i = 0;i<n;i++)mcmf::addEdge(i,i+1,q,0); for(int i = 0;i<m;i++) { string ss = ptt[i]+'#'+s; occ(ss,ptt[i],i); } mcmf::addEdge(n+1,0,q,0); mcmf::addEdge(n,n+2,q,0); pll x = mcmf::solve(); cout<<-x.ff; }
  56.  
  57.  
  58.  
  59.  
  60. max flow solution print: namespace mf { const int MAXN = 10004; struct edge { int a, b, cap, flow ; edge(int _a,int _b,int _c,int _d) { a=_a,b=_b,cap=_c,flow=_d; } } ; int INF=1500000001; int n, s, t, d [ MAXN*2 ] , ptr [ MAXN*2 ] , q [ MAXN*2*10 ] ; vector < edge > e ; vector < int > g [ MAXN * 2 ] ; void addEdge ( int a, int b, int cap ,int cap2=0) { edge e1 =edge( a, b, cap, 0 ) ; /* forward cap*/ edge e2 =edge( b, a, cap2 , 0 ) ; /* backward cap change here if needed*/ g [ a ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e1 ) ; g [ b ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e2 ) ; } bool bfs ( ) { int qh = 0 , qt = 0 ; q [ qt ++ ] = s ; memset ( d, -1 , sizeof d ) ; d [ s ] = 0 ; while ( qh < qt && d [ t ] == - 1 ) { int v = q [ qh ++ ] ; for ( size_t i = 0 ; i < g [ v ] . size ( ) ; ++ i ) { int id = g [ v ] [ i ] , to = e [ id ] . b ; if ( d [ to ] == - 1 && e [ id ] . flow < e [ id ] . cap ) { q [ qt ++ ] = to ; d [ to ] = d [ v ] + 1 ; } } } return d [ t ] != -1; } int dfs ( int v, int flow ) { if ( ! flow ) return 0 ; if ( v == t ) return flow ; for ( ; ptr [ v ] < ( int ) g [ v ] . size ( ) ; ++ ptr [ v ] ) { int id = g [ v ] [ ptr [ v ] ] , to = e [ id ] . b ; if ( d [ to ] != d [ v ] + 1 ) continue ; int pushed = dfs ( to, min ( flow, e [ id ] . cap - e [ id ] . flow ) ) ; if ( pushed ) { e [ id ] . flow += pushed ; e [ id ^ 1 ] . flow -= pushed ; return pushed ; } } return 0 ; } ll dinic ( ) { ll flow = 0 ; for ( ;; ) { if ( !bfs () ) break ; memset ( ptr, 0 , sizeof ptr ) ; while ( int pushed = dfs ( s, INF ) ) { flow += (ll)pushed ; if(pushed == 0)break; } } return flow ; } void init(int src, int dest , int nodes){ e.clear(); for(int i = 0;i<=n+n;i++) g[i].clear(); n = nodes; s = src; t = dest; } }; int prime[MAX],p,flag[MAX]; void sieve(int n){ double z = sqrt(n); for(int i = 4;i<=n;i+=2)flag[i] = 1; for(int i = 3;i<=z;i+=2){ if(!flag[i]){ for(ll j = i*i;j<=n;j+=i+i)flag[j] = 1; } } prime[p++] = 2; for(int i = 3;i<=n;i+=2){ if(!flag[i])prime[p++] = i; } } int nn,arr[MAX];vi v[MAX],ans[MAX];int vis[MAX],cnt; void dfs(int s){ if(vis[s])return ; vis[s] = 1; ans[cnt].pb(s); for(auto it : v[s]){ if(!vis[it])dfs(it); } } int main() { sieve(100000); cin>>nn; for(int i = 0;i<nn;i++){ cin>>arr[i]; } mf::init(0,nn+1,nn+3); for(int i = 0;i<nn;i++){ for(int j = i+1;j<nn;j++){ if(!flag[arr[i]+arr[j]]){ if(arr[i]&1)mf::addEdge(i+1,j+1,1); else mf::addEdge(j+1,i+1,1); } } } int pnt = 0; for(int i = 0;i<nn;i++){ if(arr[i]&1)mf::addEdge(0,i+1,2),pnt++; else mf::addEdge(i+1,nn+1,2); } int x = mf::dinic(); /*cout<<x<<endl;*/ if(x!=nn||pnt!=nn-pnt)cout<<"Impossible"; else { for(int i = 0;i<nn;i++){ int sz = mf::g[i+1].size(); for(int j = 0;j<sz;j++){ int indx = mf::g[i+1][j]; if(mf::e[indx].flow==1){ int a = mf::e[indx].a; int b = mf::e[indx].b; v[a].pb(b); v[b].pb(a); } } } for(int i = 1;i<=nn;i++){ if(!vis[i]){ cnt++; dfs(i); } } cout<<cnt<<endl; for(int i = 1;i<=cnt;i++){ cout<<ans[i].size()<<" "; for(auto it : ans[i])cout<<it<<" "; cout<<endl; } } return 0; }
  61.  
  62.  
  63.  
  64.  
  65. max flow: namespace mf { const int MAXN = 10004; struct edge { int a, b, cap, flow ; edge(int _a,int _b,int _c,int _d) { a=_a,b=_b,cap=_c,flow=_d; } } ; int INF=1500000001; int n, s, t, d [ MAXN*2 ] , ptr [ MAXN*2 ] , q [ MAXN*2*10 ] ; vector < edge > e ; vector < int > g [ MAXN * 2 ] ; void addEdge ( int a, int b, int cap ,int cap2=0) { edge e1 =edge( a, b, cap, 0 ) ; /* forward cap*/ edge e2 =edge( b, a, cap2 , 0 ) ; /* backward cap change here if needed*/ g [ a ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e1 ) ; g [ b ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e2 ) ; } bool bfs ( ) { int qh = 0 , qt = 0 ; q [ qt ++ ] = s ; memset ( d, -1 , sizeof d ) ; d [ s ] = 0 ; while ( qh < qt && d [ t ] == - 1 ) { int v = q [ qh ++ ] ; for ( size_t i = 0 ; i < g [ v ] . size ( ) ; ++ i ) { int id = g [ v ] [ i ] , to = e [ id ] . b ; if ( d [ to ] == - 1 && e [ id ] . flow < e [ id ] . cap ) { q [ qt ++ ] = to ; d [ to ] = d [ v ] + 1 ; } } } return d [ t ] != -1; } int dfs ( int v, int flow ) { if ( ! flow ) return 0 ; if ( v == t ) return flow ; for ( ; ptr [ v ] < ( int ) g [ v ] . size ( ) ; ++ ptr [ v ] ) { int id = g [ v ] [ ptr [ v ] ] , to = e [ id ] . b ; if ( d [ to ] != d [ v ] + 1 ) continue ; int pushed = dfs ( to, min ( flow, e [ id ] . cap - e [ id ] . flow ) ) ; if ( pushed ) { e [ id ] . flow += pushed ; e [ id ^ 1 ] . flow -= pushed ; return pushed ; } } return 0 ; } ll dinic ( ) { ll flow = 0 ; for ( ;; ) { if ( !bfs () ) break ; memset ( ptr, 0 , sizeof ptr ) ; while ( int pushed = dfs ( s, INF ) ) { flow += (ll)pushed ; if(pushed == 0)break; } } return flow ; } void init(int src, int dest , int nodes){ e.clear(); FOR(i,0,n+n) g[i].clear(); n = nodes; s = src; t = dest; } }; max flow (dinitz algorithm) works on undirected graph can have loops, multiple edges, cycles **/ ********* MUST be 1 indexed ********* 0 can not be a node **/ namespace mf { int src, snk, nNode, nEdge; const int MAXN = 104; const int MAXE = 20004; /* MAXE = twice the number of edges*/ int INF=1500000001; int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN]; int flow[MAXE], cap[MAXE], nextt[MAXE], to[MAXE]; inline void init(int _src, int _snk, int _n) { src = _src, snk = _snk, nNode = _n, nEdge = 0; SET(fin); } /* for directed graph _cap2 = 0*/ inline void addEdge(int u, int v, int _cap, int _cap2) { to[nEdge] = v, cap[nEdge] = _cap, flow[nEdge] = 0; nextt[nEdge] = fin[u], fin[u] = nEdge++; to[nEdge] = u, cap[nEdge] = _cap2, flow[nEdge] = 0; nextt[nEdge] = fin[v], fin[v] = nEdge++; } bool bfs() { int st, en, i, u, v; SET(dist); dist[src] = st = en = 0; Q[en++] = src; while(st < en) { u = Q[st++]; for(i=fin[u]; i>=0; i=nextt[i]) { v = to[i]; if(flow[i] < cap[i] && dist[v]==-1) { dist[v] = dist[u]+1; Q[en++] = v; } } } return dist[snk]!=-1; } int dfs(int u, int fl) { if(u==snk) return fl; for(int &e=pro[u], v, df; e>=0; e=nextt[e]) { v = to[e]; if(flow[e] < cap[e] && dist[v]==dist[u]+1) { df = dfs(v, min(cap[e]-flow[e], fl)); if(df>0) { flow[e] += df; flow[e^1] -= df; return df; } } } return 0; } ll dinitz() { ll ret = 0; ll df; for(int i=1; i<=nNode; i++) pro[i] = fin[i]; while(bfs()) { while(true) { df = dfs(src, INF); if(df) ret += df; else break; } } return ret; } }
  66.  
  67.  
  68.  
  69.  
  70. Dinic: namespace mf { const int MAXN = 10004; struct edge { int a, b, cap, flow ; edge(int _a,int _b,int _c,int _d) { a=_a,b=_b,cap=_c,flow=_d; } } ; int INF=1500000001; int n, s, t, d [ MAXN*2 ] , ptr [ MAXN*2 ] , q [ MAXN*2*10 ] ; vector < edge > e ; vector < int > g [ MAXN * 2 ] ; void addEdge ( int a, int b, int cap ,int cap2=0) { edge e1 =edge( a, b, cap, 0 ) ; /* forward cap*/ edge e2 =edge( b, a, cap2 , 0 ) ; /* backward cap change here if needed*/ g [ a ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e1 ) ; g [ b ] . push_back ( ( int ) e. size ( ) ) ; e. push_back ( e2 ) ; } bool bfs ( ) { int qh = 0 , qt = 0 ; q [ qt ++ ] = s ; memset ( d, -1 , sizeof d ) ; d [ s ] = 0 ; while ( qh < qt && d [ t ] == - 1 ) { int v = q [ qh ++ ] ; for ( size_t i = 0 ; i < g [ v ] . size ( ) ; ++ i ) { int id = g [ v ] [ i ] , to = e [ id ] . b ; if ( d [ to ] == - 1 && e [ id ] . flow < e [ id ] . cap ) { q [ qt ++ ] = to ; d [ to ] = d [ v ] + 1 ; } } } return d [ t ] != -1; } int dfs ( int v, int flow ) { if ( ! flow ) return 0 ; if ( v == t ) return flow ; for ( ; ptr [ v ] < ( int ) g [ v ] . size ( ) ; ++ ptr [ v ] ) { int id = g [ v ] [ ptr [ v ] ] , to = e [ id ] . b ; if ( d [ to ] != d [ v ] + 1 ) continue ; int pushed = dfs ( to, min ( flow, e [ id ] . cap - e [ id ] . flow ) ) ; if ( pushed ) { e [ id ] . flow += pushed ; e [ id ^ 1 ] . flow -= pushed ; return pushed ; } } return 0 ; } ll dinic ( ) { ll flow = 0 ; for ( ;; ) { if ( !bfs () ) break ; memset ( ptr, 0 , sizeof ptr ) ; while ( int pushed = dfs ( s, INF ) ) { flow += (ll)pushed ; if(pushed == 0)break; } } return flow ; } void init(int src, int dest , int nodes){ e.clear(); FOR(i,0,n+n) g[i].clear(); n = nodes; s = src; t = dest; } }; max flow (dinitz algorithm) works on undirected graph can have loops, multiple edges, cycles **/ ********* MUST be 1 indexed ********* 0 can not be a node **/ namespace mf { int src, snk, nNode, nEdge; const int MAXN = 104; const int MAXE = 20004; /* MAXE = twice the number of edges*/ int INF=1500000001; int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN]; int flow[MAXE], cap[MAXE], nextt[MAXE], to[MAXE]; inline void init(int _src, int _snk, int _n) { src = _src, snk = _snk, nNode = _n, nEdge = 0; SET(fin); } /* for directed graph _cap2 = 0*/ inline void addEdge(int u, int v, int _cap, int _cap2) { to[nEdge] = v, cap[nEdge] = _cap, flow[nEdge] = 0; nextt[nEdge] = fin[u], fin[u] = nEdge++; to[nEdge] = u, cap[nEdge] = _cap2, flow[nEdge] = 0; nextt[nEdge] = fin[v], fin[v] = nEdge++; } bool bfs() { int st, en, i, u, v; SET(dist); dist[src] = st = en = 0; Q[en++] = src; while(st < en) { u = Q[st++]; for(i=fin[u]; i>=0; i=nextt[i]) { v = to[i]; if(flow[i] < cap[i] && dist[v]==-1) { dist[v] = dist[u]+1; Q[en++] = v; } } } return dist[snk]!=-1; } int dfs(int u, int fl) { if(u==snk) return fl; for(int &e=pro[u], v, df; e>=0; e=nextt[e]) { v = to[e]; if(flow[e] < cap[e] && dist[v]==dist[u]+1) { df = dfs(v, min(cap[e]-flow[e], fl)); if(df>0) { flow[e] += df; flow[e^1] -= df; return df; } } } return 0; } ll dinitz() { ll ret = 0; ll df; for(int i=1; i<=nNode; i++) pro[i] = fin[i]; while(bfs()) { while(true) { df = dfs(src, INF); if(df) ret += df; else break; } } return ret; } }const int MAX=10100; int que[MAX]; template <class T> struct Edge { int to, next; T cap, flow; Edge(int to, int next, T cap) { this->to = to; this->next = next; this->cap = cap; this->flow = 0; } }; template <class T> struct Dinic { T INF; const int nodes; int source, sink, lvl[MAX], nodeEnd[MAX], last[MAX]; vector < Edge <T> > edgeList; Dinic(int n) : nodes(n), INF(numeric_limits<T>::max() / 4) { fill(nodeEnd, nodeEnd+n, -1); } void addEdge(int u, int v, T cap = 1) { edgeList.push_back(Edge<T> (v, nodeEnd[u], cap)); nodeEnd[u] = (int)edgeList.size()-1; edgeList.push_back(Edge<T> (u, nodeEnd[v], 0)); nodeEnd[v] = (int)edgeList.size()-1; } /* bfs*/ bool createLevel() { memset(lvl, -1, nodes * sizeof(int)); int qs = 0, qt = 0; que[qs] = source, lvl[source] = 0; while(qs <= qt) { int nd = que[qs++], ch; for(int i = nodeEnd[nd]; i != -1; i = edgeList[i].next) if(lvl[ch = edgeList[i].to] == -1 && edgeList[i].cap > edgeList[i].flow) lvl[ch] = lvl[nd] + 1, que[++qt] = ch; } return lvl[sink] != -1; } /* dfs*/ T blockingFlow(int nd, T flow) { if(nd == sink) return flow; int ch; T pflow = flow; for(int &i = last[nd]; i != -1; i = edgeList[i].next) if(lvl[ch = edgeList[i].to] == lvl[nd]+1) { T pushed = blockingFlow(ch, min(pflow, edgeList[i].cap - edgeList[i].flow)); pflow -= pushed; edgeList[i].flow += pushed; edgeList[i ^ 1].flow -= pushed; if(!pflow) break; } return flow - pflow; } T maxFlow(int src, int snk) { /*REP(i, edgeList.size()) edgeList[i].flow = 0;*/ source = src, sink = snk; T tot = 0; while(createLevel()) { memcpy(last, nodeEnd, nodes * sizeof(int)); tot += blockingFlow(source, INF); } return tot; } };
  71.  
  72.  
  73.  
  74.  
  75. max match solution print: const int MAXN1 = 50000; const int MAXN2 = 50000; const int MAXM = 150000; int n1, n2, edges, last[MAXN1], prv[MAXM], head[MAXM]; int matching[MAXN2], dist[MAXN1], Q[MAXN1]; bool used[MAXN1], vis[MAXN1]; void init(int _n1, int _n2) { n1 = _n1; n2 = _n2; edges = 0; fill(last, last + n1, -1); } void addEdge(int u, int v) { head[edges] = v; prv[edges] = last[u]; last[u] = edges++; } void bfs() { fill(dist, dist + n1, -1); int sizeQ = 0; for (int u = 0; u < n1; ++u) { if (!used[u]) { Q[sizeQ++] = u; dist[u] = 0; } } for (int i = 0; i < sizeQ; i++) { int u1 = Q[i]; for (int e = last[u1]; e >= 0; e = prv[e]) { int u2 = matching[head[e]]; if (u2 >= 0 && dist[u2] < 0) { dist[u2] = dist[u1] + 1; Q[sizeQ++] = u2; } } } } bool dfs(int u1) { vis[u1] = true; for (int e = last[u1]; e >= 0; e = prv[e]) { int v = head[e]; int u2 = matching[v]; if (u2 < 0 || !vis[u2] && dist[u2] == dist[u1] + 1 && dfs(u2)) { matching[v] = u1; used[u1] = true; return true; } } return false; } int maxMatching() { fill(used, used + n1, false); fill(matching, matching + n2, -1); for (int res = 0;;) { bfs(); fill(vis, vis + n1, false); int f = 0; for (int u = 0; u < n1; ++u) if (!used[u] && dfs(u)) ++f; if (!f) return res; res += f; } } int arr1[200],arr2[200]; int main() { int t; scani(t); int ajinka=1; while(t--) { init(500, 500); int n,m; scani(n); int arr[n+5]; for(int i=0;i<n;i++)scani(arr[i]); sort(arr,arr+n); int x=unique(arr,arr+n)-arr; for(int i=0;i<x;i++)for(int j=i+1;j<x;j++)if(arr[j]%arr[i]==0)addEdge(i,j); int mis=x-maxMatching();int prr[n+5];vi ans;mem(prr,0); for(int i=0;i<x;i++) { if(prr[i])continue; vi pk; pk.pb(arr[i]); for(int j=i+1;j<x;j++) { if(prr[j]==0&&arr[j]%arr[i]!=0) pk.pb(arr[j]); } init(300,300); int mnt = 0; for(int j=0;j<pk.size();j++)for(int k=j+1;k<pk.size();k++)if(pk[k]%pk[j]==0)addEdge(j,k); int gg = ans.size() + pk.size() - maxMatching(); if (gg == mis) { ans.pb(arr[i]); for(int j=i+1;j<x;j++)if(arr[j]%arr[i]==0)prr[j]=1; } } printf("Case %d: ",ajinka++); for(int j=0;j<ans.size();j++) { printf("%d",ans[j]); if(j<ans.size()-1)printf(" "); } printf("\n"); } return 0; }
  76.  
  77.  
  78.  
  79.  
  80. aho corasick and dp: int l,r,k,n,m;int sz;int ending[1005];int to[1005][50],link[1005];string ss[1005],str;int dp[1005][1005],vis[1005][1005]; void Insert(string s,int indx){ int curr = 0; int len = s.length(); for(int i = 0;i<len;i++){ int id = s[i] - 97; if(!to[curr][id])to[curr][id] = ++sz; curr = to[curr][id]; } ending[curr]++; } void failure() { int curr = 0; link[curr] = -1; queue<int>q; q.push(curr); while(!q.empty()){ int x = q.front(); q.pop(); for(int i = 0;i<26;i++){ if(!to[x][i])continue; if(!x)link[to[x][i]] = 0; else { int y = x; while(link[y]!=-1){ if(to[link[y]][i]){ link[to[x][i]] = to[link[y]][i]; break; } y = link[y]; } if(link[y]==-1)link[to[x][i]] = 0; } ending[to[x][i]]+=ending[link[to[x][i]]]; q.push(to[x][i]); } } } void CLEAR() { for(int i = 0;i<1005;i++){ for(int j = 0;j<1005;j++){ dp[i][j] = -1;to[i][j] = vis[i][j] = 0; } link[i] = ending[i] = 0; } sz = 0; } void print(int pos,int id) { if(pos==n)return; int &ret = vis[pos][id]; if(ret!=0)return ; ret = 1; int pk = str[pos] - 97; if(str[pos]=='?'){ int mx = -1,ik,st; for(int i = 0;i<26;i++){ int state = id; while(state!=-1&&to[state][i]==0)state = link[state]; if(state==-1)state = 0; state = to[state][i]; int x = dp[pos+1][state]+ending[state]; if(x>mx){ mx = x; ik = i; st = state; } } cout<<(char)(ik+'a'); print(pos+1,st); } else { int state = id; while(state!=-1&&to[state][pk]==0)state = link[state]; if(state==-1)state = 0; state = to[state][pk]; cout<<str[pos]; print(pos+1,state); } } int giveres(int pos,int id){ if(pos==n)return 0; int &ret = dp[pos][id]; if(ret!=-1)return ret; ret = 0; int pk = str[pos] - 'a'; if(str[pos]=='?'){ for(int i = 0;i<26;i++){ int state = id; while(state!=-1&&to[state][i]==0)state = link[state]; if(state==-1)state = 0; state = to[state][i]; ret = max(ret,giveres(pos+1,state)+ending[state]); } } else { int state = id; while(state!=-1&&to[state][pk]==0)state = link[state]; if(state==-1)state = 0; state = to[state][pk]; ret = max(ret,giveres(pos+1,state)+ending[state]); } return ret; } int main() { int t; cin>>t; while(t--){ CLEAR(); cin>>n>>m; cin>>str; for(int i = 0;i<m;i++){ cin>>ss[i]; Insert(ss[i],i); } failure(); cout<<giveres(0,0)<<endl; for(int i = 0;i<1005;i++)for(int j = 0;j<1005;j++)if(dp[i][j]==-1)dp[i][j] = 0; print(0,0); cout<<endl; }
  81.  
  82.  
  83.  
  84.  
  85. aho corasick without pointer: const int maxn = 160 * 80;/* sum of length of all patterns...*/ string ss[MAX],str;int sz,to[maxn][30],link[maxn];vi ending[maxn];int End[200],len; void CLEAR(){ sz = 0; mem(to,0); mem(link,0); mem(End,0); for(int i = 0;i<maxn;i++)ending[i].clear(); } void Insert(string s,int indx){ int curr = 0; for(int i = 0;i<(int)s.length();i++){ int id = s[i] - 'a'; if(!to[curr][id])to[curr][id] = ++sz; curr = to[curr][id]; } ending[curr].pb(indx); } void propagate(int pos){ for(auto it : ending[link[pos]]){ ending[pos].pb(it); } } void failure() { int curr = 0; link[curr] = -1; queue<int>q; q.push(curr); while(!q.empty()){ int x = q.front(); q.pop(); for(int i = 0;i<26;i++){ if(!to[x][i])continue; if(!x)link[to[x][i]] = 0; else { int y = x; while(link[y]!=-1){ if(to[link[y]][i]){ link[to[x][i]] = to[link[y]][i]; break; } y = link[y]; } if(link[y]==-1)link[to[x][i]] = 0; } propagate(to[x][i]); q.push(to[x][i]); } } } void Search(){ int curr = 0; int indx = 0; while(indx<len){ int id = str[indx] - 'a'; while(curr!=-1&&!to[curr][id])curr = link[curr]; if(curr==-1)curr = 0; curr = to[curr][id]; for(int i = 0;i<ending[curr].size();i++){ End[ending[curr][i]]++; } indx++; } } int main() { while(1){ CLEAR(); int n; cin>>n; if(!n)break; for(int i = 0;i<n;i++){ cin>>ss[i]; Insert(ss[i],i); } failure(); cin>>str; len = str.length(); Search(); int mx = 0; for(int i = 0;i<n;i++){ mx = max(mx,End[i]); } cout<<mx<<endl; for(int i = 0;i<n;i++){ if(mx==End[i])cout<<ss[i]<<endl; } } return 0; }
  86.  
  87.  
  88.  
  89.  
  90. cut node: int ans,vis[mx],low[mx],d[mx],par[mx],pkkkkk,arr[mx];vector<int>v[mx]; void dfs(int s,int flag) { pkkkkk=pkkkkk+1; int child=0; d[s]=low[s]=pkkkkk; vis[s]=1; for(int i=0;i<v[s].size();i++) { int u=v[s][i]; if(u==par[s])continue; if(vis[u]==1) { low[s]=min(low[s],d[u]); } else { par[u]=s; dfs(u,0); low[s]=min(low[u],low[s]); if(low[u]>=d[s]&&flag==0) { arr[s]=1; } child=child+1; } } if(child>1&&flag==1) { arr[s]=1; } } int main() { int t; scanf("%d",&t); for(int q=0;q<t;q++) { int n,m;pkkkkk=0; scanf("%d%d",&n,&m); ans=0; for(int i=1;i<=n;i++) { vis[i]=0; v[i].clear(); arr[i]=0; } for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } for(int i=1;i<=n;i++) { if(!vis[i])dfs(i,1); } for(int i=1;i<=n;i++) { if(arr[i])ans++; } printf("Case %d: %d\n",q+1,ans); } }
  91.  
  92.  
  93.  
  94.  
  95. bridge: int ans,vis[mx],low[mx],d[mx],par[mx],pkkkkk,arr[mx];vector<int>v[mx];set<pii>st; set<pii>::iterator it; void dfs(int s) { pkkkkk=pkkkkk+1; d[s]=low[s]=pkkkkk; vis[s]=1; for(int i=0;i<v[s].size();i++) { int u=v[s][i]; if(u==par[s])continue; if(vis[u]==1) { low[s]=min(low[s],d[u]); } else { par[u]=s; dfs(u); low[s]=min(low[u],low[s]); if(low[u]>d[s]) { st.insert(pii(min(s,u),max(s,u))); } } } } int main() { int t; scanf("%d",&t); for(int q=0;q<t;q++) { int n,m;pkkkkk=0; scanf("%d",&n); ans=0;st.clear(); for(int i=0;i<=n;i++) { vis[i]=0; v[i].clear(); } for(int i=0;i<n;i++) { int nodeno,son,a; scanf("%d (%d)",&nodeno,&son); for(int j=0;j<son;j++) { scanf("%d",&a); v[nodeno].push_back(a); } } for(int i=0;i<=n;i++) { if(!vis[i])dfs(i); } printf("Case %d:\n",q+1); printf("%d critical links\n",st.size()); for(it=st.begin();it!=st.end();it++) { printf("%d - %d\n",it->first,it->second); } } }
  96.  
  97.  
  98.  
  99.  
  100. HLD: int base[mx],tree[6*mx],level[mx],parent[mx],SubtrSiz[mx],arr[mx];vector<int>adj[mx]; int chainLeader[mx],chain[mx],basepos[mx],ptr=1,ch; void Build(int node,int b,int e) { if(b==e) { tree[node]=base[b]; return; } int mid=(b+e)/2; int left=2*node; int right=left+1; Build(left,b,mid); Build(right,mid+1,e); tree[node]=tree[left]+tree[right]; } int query(int node,int b,int e,int l,int r) { if(b>r||l>e)return 0; if(b>=l&&e<=r)return tree[node]; int mid=(b+e)/2; int left=2*node; int right=left+1; int p1=query(left,b,mid,l,r); int p2=query(right,mid+1,e,l,r); return p1+p2; } void update(int node,int b,int e,int newVal,int pos) { if(b>pos||e<pos)return; if(b==e) { base[b]=newVal; tree[node]=base[b]; return; } int mid=(b+e)/2; int left=2*node; int right=left+1; update(left,b,mid,newVal,pos); update(right,mid+1,e,newVal,pos); tree[node]=tree[left]+tree[right]; } int dfs(int s,int lev,int pr) { level[s]=lev; parent[s]=pr; SubtrSiz[s]=1; for(int i=0;i<adj[s].size();i++) { int u=adj[s][i]; if(u!=parent[s]) { SubtrSiz[s]+=dfs(u,lev+1,s); } } return SubtrSiz[s]; } void HLD(int node,int chainNo,int cst,bool isL) { if(isL) { chainNo=++ch; chainLeader[chainNo]=node; } chain[node]=chainNo; basepos[node]=ptr; base[ptr++]=cst; int Heavy=-1,Heavynode,Heavycost; for(int i=0;i<adj[node].size();i++) { int u=adj[node][i]; if(u==parent[node])continue; if(SubtrSiz[u]>Heavy) { Heavy=SubtrSiz[u]; Heavynode=u; Heavycost=arr[u]; } } if(Heavy==-1)return; HLD(Heavynode,chainNo,Heavycost,false); for(int i=0;i<adj[node].size();i++) { int u=adj[node][i]; int w=arr[u]; if(u==parent[node]||u==Heavynode)continue; HLD(u,0,w,true); } } int lca(int u,int v) { while(chain[u]!=chain[v]) { if(level[chainLeader[chain[u]]]>level[chainLeader[chain[v]]]) { u=parent[chainLeader[chain[u]]]; } else v=parent[chainLeader[chain[v]]]; } if(level[u]<level[v])return u; else return v; } int query_up(int u,int v) { int maxi=0; while(1) { if(chain[u]==chain[v]) { int x=query(1,1,ptr,min(basepos[u],basepos[v]),max(basepos[u],basepos[v])); maxi+=x; break; } int y=query(1,1,ptr,min(basepos[u],basepos[chainLeader[chain[u]]]),max(basepos[u],basepos[chainLeader[chain[u]]])); maxi+=y; u=parent[chainLeader[chain[u]]]; } return maxi; } int giveres(int node1,int node2) { int LCA=lca(node1,node2); int max1=query_up(node1,LCA); int max2=query_up(node2,LCA); return max1+max2-base[basepos[LCA]]; } int main() { int t; scanf("%d",&t); for(int q=0;q<t;q++) { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&arr[i]); int root=1; for(int i=0;i<=n;i++) { adj[i].clear(); } ptr=1;ch=0; for(int i=0;i<n-1;i++) { int a,b,c; scanf("%d%d",&a,&b); a++;b++; adj[a].push_back(b); adj[b].push_back(a); root=1; } dfs(root,1,root); HLD(root,0,arr[1],true); ptr--; Build(1,1,ptr); int qt; scanf("%d",&qt); printf("Case %d:\n",q+1); for(int i=0;i<qt;i++) { int cho; scanf("%d",&cho); if(cho==0) { int node1,node2; scanf("%d%d",&node1,&node2); node1++;node2++; printf("%d\n",giveres(node1,node2)); } else { int ed,val; scanf("%d%d",&ed,&val); ed++; arr[ed]=val; update(1,1,ptr,val,basepos[ed]); } } } }
  101.  
  102.  
  103.  
  104.  
  105. Centroid Decomposition: int par[MAX],lev[MAX],table[MAX][25];vi v[MAX],tree[MAX];int root;int Subtree[MAX],del[MAX],n,totalnode,parent[MAX],level[MAX],res;multiset<int >ans[MAX]; void dfs1(int s,int p,int l) { par[s] = p; lev[s] = l; for(auto it : v[s]) { if(it==p)continue; dfs1(it,s,l+1); } } void lca_init() { for(int i = 1;i<=n;i++) { table[i][0] = par[i]; } for(int i = 1;i<=n;i++) { for(int j = 1;(1<<j)<=n;j++) { if(table[i][j-1]!=-1) { table[i][j] = table[table[i][j-1]][j-1]; } } } } int lca_query(int uu,int vv) { if(lev[vv]<lev[uu])swap(uu,vv); int log = 1; while((1<<log)<lev[vv])log++; for(int i = log;i>=0;i--) { if(lev[vv] - (1<<i)>=lev[uu]) { vv = table[vv][i]; } } if(uu==vv)return uu; for(int i = log;i>=0;i--) { if(table[vv][i]!=-1&&table[vv][i]!=table[uu][i]) { vv = table[vv][i]; uu = table[uu][i]; } } return par[uu]; } void dfs2(int s,int p) { Subtree[s] = 1; totalnode++; for(auto it : v[s]) { if(it==p||del[it])continue; dfs2(it,s); Subtree[s]+=Subtree[it]; } } int Getcenter(int s,int p) { for(auto it : v[s]) { if(it==p||del[it])continue; if(Subtree[it]>totalnode/2)return Getcenter(it,s); } return s; } void Decompose(int x,int p) { totalnode = 0; dfs2(x,p); int s = Getcenter(x,p); del[s] = 1; if(p>0) { tree[s].pb(p); tree[p].pb(s); } else root = s; for(auto it : v[s]) { if(it==p||del[it])continue; Decompose(it,s); } } int distance(int uu,int vv){return lev[uu]+lev[vv] - 2* lev[lca_query(uu,vv)];} int colour[MAX]; void change0(int u,int p) { if(u==-1)return ; ans[u].insert(distance(u,p)); change0(parent[u],p); } void change1(int u,int p) { if(u==-1)return ; ans[u].erase(ans[u].find(distance(u,p))); change1(parent[u],p); } void query(int u,int p) { if(u==-1)return ; res = min(res,*ans[u].begin()+distance(u,p)); query(parent[u],p); } void dfs3(int s,int p,int l = 0) { parent[s] = p; level[s] = l; for(auto it : tree[s]) { if(it==p)continue; dfs3(it,s,l+1); } } int main() { cin>>n; for(int i = 0;i<n-1;i++) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } dfs1(1,-1,0); lca_init(); Decompose(1,-1); dfs3(root,-1); int q; cin>>q; for(int i = 1;i<=n;i++)colour[i] = 1,ans[i].insert(inf/10); while(q--) { int ch,vv; cin>>ch>>vv; res = inf/10; if(ch==0) { if(colour[vv]==0) { colour[vv] = 1; change1(vv,vv); } else { colour[vv] = 0; change0(vv,vv); } } else { query(vv,vv); if(res>=inf/10)res = -1; cout<<res<<endl; } } }
  106.  
  107.  
  108.  
  109.  
  110. lca + sparse table: int par[MAX],lev[MAX],table[MAX][25];vi v[MAX],tree[MAX];int root;int Subtree[MAX],del[MAX],n,totalnode,parent[MAX],level[MAX],res;multiset<int >ans[MAX]; void dfs1(int s,int p,int l) { par[s] = p; lev[s] = l; for(auto it : v[s]) { if(it==p)continue; dfs1(it,s,l+1); } } void lca_init() { for(int i = 1;i<=n;i++) { table[i][0] = par[i]; } for(int i = 1;i<=n;i++) { for(int j = 1;(1<<j)<=n;j++) { if(table[i][j-1]!=-1) { table[i][j] = table[table[i][j-1]][j-1]; } } } } int lca_query(int uu,int vv) { if(lev[vv]<lev[uu])swap(uu,vv); int log = 1; while((1<<log)<lev[vv])log++; for(int i = log;i>=0;i--) { if(lev[vv] - (1<<i)>=lev[uu]) { vv = table[vv][i]; } } if(uu==vv)return uu; for(int i = log;i>=0;i--) { if(table[vv][i]!=-1&&table[vv][i]!=table[uu][i]) { vv = table[vv][i]; uu = table[uu][i]; } } return par[uu]; } void dfs2(int s,int p) { Subtree[s] = 1; totalnode++; for(auto it : v[s]) { if(it==p||del[it])continue; dfs2(it,s); Subtree[s]+=Subtree[it]; } } int Getcenter(int s,int p) { for(auto it : v[s]) { if(it==p||del[it])continue; if(Subtree[it]>totalnode/2)return Getcenter(it,s); } return s; } void Decompose(int x,int p) { totalnode = 0; dfs2(x,p); int s = Getcenter(x,p); del[s] = 1; if(p>0) { tree[s].pb(p); tree[p].pb(s); } else root = s; for(auto it : v[s]) { if(it==p||del[it])continue; Decompose(it,s); } } int distance(int uu,int vv){return lev[uu]+lev[vv] - 2* lev[lca_query(uu,vv)];} int colour[MAX]; void change0(int u,int p) { if(u==-1)return ; ans[u].insert(distance(u,p)); change0(parent[u],p); } void change1(int u,int p) { if(u==-1)return ; ans[u].erase(ans[u].find(distance(u,p))); change1(parent[u],p); } void query(int u,int p) { if(u==-1)return ; res = min(res,*ans[u].begin()+distance(u,p)); query(parent[u],p); } void dfs3(int s,int p,int l = 0) { parent[s] = p; level[s] = l; for(auto it : tree[s]) { if(it==p)continue; dfs3(it,s,l+1); } } int main() { cin>>n; for(int i = 0;i<n-1;i++) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } dfs1(1,-1,0); lca_init(); Decompose(1,-1); dfs3(root,-1); int q; cin>>q; for(int i = 1;i<=n;i++)colour[i] = 1,ans[i].insert(inf/10); while(q--) { int ch,vv; cin>>ch>>vv; res = inf/10; if(ch==0) { if(colour[vv]==0) { colour[vv] = 1; change1(vv,vv); } else { colour[vv] = 0; change0(vv,vv); } } else { query(vv,vv); if(res>=inf/10)res = -1; cout<<res<<endl; } } }vector<pii>v[MAX];int mata[MAX],edge[2001][2001],table[2001][50],Mx[2001][50],par[2001],cost[2001],lev[2001],vis[2001]; int findMata(int s) { if(mata[s]==s)return s; return mata[s] = findMata(mata[s]); } void dfs(int s,int p,int l,int w = 0) { par[s] = p; cost[s] = w; lev[s] = l; vis[s] = 1; for(auto it : v[s]) { if(it.ff==p)continue; dfs(it.ff,s,l+1,it.ss); } } void lca_init(int n) { for(int i = 1;i<=n;i++) { table[i][0] = par[i]; Mx[i][0] = cost[i]; } for(int i = 1;i<=n;i++) { for(int j = 1;(1<<j)<=n;j++) { if(table[i][j-1]!=-1) { table[i][j] = table[table[i][j-1]][j-1]; Mx[i][j] = max(Mx[i][j-1],Mx[table[i][j-1]][j-1]); } } } } int lca_query(int uu,int vv) { if(lev[vv]<lev[uu])swap(uu,vv); int log = 1; while((1<<log)<lev[vv])log++; int mx = 0; for(int i = log;i>=0;i--) { if(lev[vv] - (1<<i)>=lev[uu]) { mx = max(mx,Mx[vv][i]); vv = table[vv][i]; } } if(uu==vv)return mx; for(int i = log;i>=0;i--) { if(table[vv][i]!=-1&&table[vv][i]!=table[uu][i]) { mx = max3(mx,Mx[vv][i],Mx[uu][i]); vv = table[vv][i]; uu = table[uu][i]; } } return max3(mx,cost[vv],cost[uu]); } void CLEAR() { for(int i = 1;i<=2000;i++)v[i].clear(); mem(edge,0); mem(table,0); mem(Mx,0); mem(par,0); mem(cost,0); mem(lev,0); mem(vis,0); } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { CLEAR(); priority_queue<piii,vector<piii>,greater<piii> >pq; for(int i = 1;i<=n;i++)mata[i] = i; for(int i = 0;i<m;i++) { int u,v,l; scani3(u,v,l); pq.push(piii(l,pii(u,v))); } ll ans = 0; piii save; vector<piii>temp;int mx = 0; while(!pq.empty()) { piii x = pq.top(); pq.pop(); save = x; int xx = findMata(x.ss.ff); int yy = findMata(x.ss.ss); if(xx!=yy) { mata[xx] = yy; ans+=x.ff; v[x.ss.ff].pb(pii(x.ss.ss,x.ff)); v[x.ss.ss].pb(pii(x.ss.ff,x.ff)); edge[x.ss.ff][x.ss.ss] = x.ff; edge[x.ss.ss][x.ss.ff] = x.ff; mx = max(mx,x.ff); } else temp.pb(x); } dfs(1,0,0); int flag = 0; for(int i = 1;i<=n;i++) { if(!vis[i]) { flag = 1; break; } } if(flag) { printf("disconnected\n"); } else { lca_init(n); ll res = ans - 2*mx; for(int i = 0;i<temp.size();i++) { piii x = temp[i]; int pk = lca_query(x.ss.ff,x.ss.ss); res = min(res,ans - pk - x.ff); } printf("%I64d\n",res); } } return 0; }
  111.  
  112.  
  113.  
  114.  
  115. Gauss: int n ,tot[MAX],pos[MAX]; double edge[MAX][MAX],res[MAX];vector<pii>v[MAX]; int gauss(int row,int col) { mem(pos,-1); int free_var = 0; for(int i = 1,j = 1;i<=row,j<=col;i++,j++) { int mx = i; for(int k = i;k<=row;k++)if(abs(edge[mx][j])<abs(edge[k][j])) mx = k; if(abs(edge[mx][j])>EPS) { pos[j] = i; for(int l = j;l<=col;l++)swap(edge[i][l],edge[mx][l]); for(int l = 1;l<=row;l++) { if(l==i)continue; double xx = edge[l][j] / edge[i][j]; for(int pp = j;pp<=col;pp++)edge[l][pp]-=(edge[i][pp]*xx); } } } for(int l = 1;l<col;l++) { if(pos[l]==-1)free_var++; else res[l] = edge[pos[l]][col]/edge[pos[l]][l]; } for(int i = 1;i<=row;i++) { double val = 0.0; for(int j = 1;j<col;j++)val+=(res[j]*edge[i][j]); if(abs(val - edge[i][col])>EPS)return -1; } return free_var; }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!