代码：
由乃：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int N=100050;
int n,m,v,f[1050][20],tr[N*4],lazy[N*4],a[N],tot,b[N],flg,sum[N];
bool cmp(int a,int b){return a>b;}
void update(int x,int l,int r,int xl,int xr){
if(xl<=l&&r<=xr) {tr[x]++;lazy[x]++;return;}
int mid=(l+r)>>1;
if(xr<=mid) update(lson,l,mid,xl,xr);
else if(xl>mid) update(rson,mid+1,r,xl,xr);
else update(lson,l,mid,xl,mid),update(rson,mid+1,r,mid+1,xr);
}
int query(int x,int l,int r,int id,int la){
if(l==r) return tr[x]+la;
int mid=(l+r)>>1;la+=lazy[x];
if(id<=mid) return query(lson,l,mid,id,la);
else return query(rson,mid+1,r,id,la);
}
int work(int i){
int ret=query(1,1,n,i,0);int x=a[i];
for(int j=18;j>=0;j--){
if(ret>=(1<<j)) ret-=(1<<j),x=f[x][j];
}
return x;
}
void dfs(int x,int suma,int sumb,int sa,int sb){
if(abs(suma-sumb)>sum[x]+(tot-x+1)) return;
if(flg) return;
if(suma==sumb&&sa&&sb) {flg=1;return;}
if(x>tot) return;
dfs(x+1,suma+b[x]+1,sumb,sa+1,sb);
dfs(x+1,suma,sumb+b[x]+1,sa,sb+1);
dfs(x+1,suma,sumb,sa,sb);
}
int main(){
scanf("%d%d%d",&n,&m,&v);
for(int i=0;i<=v;i++) f[i][0]=(1ll*i*i*i)%v;
for(int j=1;j<=18;j++){
for(int i=0;i<=v;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
for(int i=1;i<=n;i++) scanf("%d",&a[i]);int tmp=0;
for(int i=1;i<=m;i++){
int type,l,r;scanf("%d%d%d",&type,&l,&r);
if(type==2) update(1,1,n,l,r);
else {
tmp++;
if(r-l+1>13) puts("Yuno");
else{
tot=0;
for(int j=l;j<=r;j++) b[++tot]=work(j);
sort(b+1,b+1+tot,cmp);sum[tot]=b[tot];sum[tot+1]=0;
for(int j=tot-1;j;j--) sum[j]=sum[j+1]+b[j];
flg=0;dfs(1,0,0,0,0);
if(flg) puts("Yuno");
else puts("Yuki");
}
}
}
return 0;
}
树：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const int N=300050;
int head[N],to[N],nxt[N],v[N],cnt,n,s;
ll dep[N],ans;
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
map<ll,int>Map;
void dfs(int x,int fa){
Map[dep[fa]+s]++;ans+=Map[dep[x]];
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==fa) continue;
dep[y]=dep[x]+v[y];dfs(y,x);
}
Map[dep[fa]+s]--;
}
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<n;i++) {int x,y;scanf("%d%d",&x,&y);lnk(x,y);}
dep[1]=v[1];dfs(1,0);
printf("%lld
",ans);
return 0;
}
simple:
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=500050;
int head[N],to[N],nxt[N],hsh[N],tot,rt[N],cnt,sz,a[N],n,Q;
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
int size[N],son[N],dfn[N],id[N],tt,top[N],fa[N],deep[N];
int sum[N*8],ls[N*8],rs[N*8];
char s[N];
struct data{
int type,i,j,x;
}q[N];
void dfs1(int x,int f){
size[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==f) continue;
fa[y]=x;deep[y]=deep[x]+1;dfs1(y,x);size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x,int f){
dfn[x]=++tt;top[x]=f;id[tt]=x;
if(son[x]) dfs2(son[x],f);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void update(int &x,int l,int r,int id,int v){
if(!x) x=++sz;
if(l==r) {sum[x]+=v;return;}
int mid=(l+r)>>1;
if(id<=mid) update(ls[x],l,mid,id,v);
else update(rs[x],mid+1,r,id,v);
sum[x]=sum[ls[x]]+sum[rs[x]];
}
int query(int x,int l,int r,int xl,int xr){
if(xl<=l&&r<=xr) return sum[x];
int mid=(l+r)>>1;
if(xr<=mid) return query(ls[x],l,mid,xl,xr);
else if(xl>mid) return query(rs[x],mid+1,r,xl,xr);
else return query(ls[x],l,mid,xl,mid)+query(rs[x],mid+1,r,mid+1,xr);
}
void Change(int x,int c){
update(rt[a[x]],1,n,dfn[x],-1);
update(rt[c],1,n,dfn[x],1);
a[x]=c;
}
int Query(int x,int y,int c){
int ret=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ret+=query(rt[c],1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(deep[x]<deep[y]) swap(x,y);
ret+=query(rt[c],1,n,dfn[y],dfn[x]);
return ret;
}
int main(){
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),hsh[++tot]=a[i];
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);lnk(x,y);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=Q;i++){
scanf("%s",s+1);
if(s[1]=='Q') scanf("%d%d%d",&q[i].i,&q[i].j,&q[i].x),q[i].type=1,hsh[++tot]=q[i].x;
else scanf("%d%d",&q[i].i,&q[i].x),q[i].type=2,hsh[++tot]=q[i].x;
}
sort(hsh+1,hsh+1+tot);tot=unique(hsh+1,hsh+1+tot)-hsh-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(hsh+1,hsh+1+tot,a[i])-hsh,update(rt[a[i]],1,n,dfn[i],1);
for(int i=1;i<=Q;i++){
q[i].x=lower_bound(hsh+1,hsh+1+tot,q[i].x)-hsh;
if(q[i].type==1) printf("%d
",Query(q[i].i,q[i].j,q[i].x));
else Change(q[i].i,q[i].x);
}
return 0;
}
oi树：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=10050;
int f[N][27][33],g[N][27][33];
int n,k,son[N][27],v[N][27],mod;
char s[N*20];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
scanf("%d%d",&son[i][j-1],&v[i][j-1]);
f[i][j-1][0]=son[i][j-1],g[i][j-1][0]=v[i][j-1];
}
}
scanf("%s",s+1);scanf("%d",&mod);
for(int j=1;j<=31;j++){
for(int K=0;K<k;K++){
for(int i=1;i<=n;i++){
f[i][K][j]=f[f[i][K][j-1]][K][j-1];
g[i][K][j]=(g[i][K][j-1]+g[f[i][K][j-1]][K][j-1])%mod;
}
}
}
int len=strlen(s+1),ans=0,x=1,i=1;
for(int i=1;i<=len;i++){
if(s[i]=='['){
int p=0;
while(s[++i]>='0'&&s[i]<='9') p=p*10+s[i]-48;
int K=s[i]-'A';
i++;
for(int j=31;j>=0;j--){
if(p>=(1ll<<j)&&f[x][K][j]){
(ans+=g[x][K][j])%=mod;
p-=(1<<j);x=f[x][K][j];
}
}
}
else{
int K=s[i]-'A';
(ans+=g[x][K][0])%=mod;x=f[x][K][0];
}
}
cout<<ans%mod<<endl;
return 0;
}
二分图：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int N=1000050;
struct data{
int u,v;
};
vector<data> p[N];
int dep[N],sz[N],fa[N],a[N],top,n,m,T;
struct date{
int x,y,a,sz;
}zhan[N];
void query(int x,int l,int r,int xl,int xr,int u,int v){
if(xl<=l&&r<=xr) {p[x].push_back((data){u,v});return;}
int mid=(l+r)>>1;
if(xr<=mid) query(lson,l,mid,xl,xr,u,v);
else if(xl>mid) query(rson,mid+1,r,xl,xr,u,v);
else query(lson,l,mid,xl,mid,u,v),query(rson,mid+1,r,mid+1,xr,u,v);
}
int find(int x){
if(x==fa[x]) return fa[x];int y=find(fa[x]);
dep[x]=dep[fa[x]]^a[x];return y;
}
int merge(int x,int y){
int u=find(x),v=find(y);
if(u==v) return dep[x]^dep[y]^1;
if(sz[u]>sz[v]) swap(u,v);
zhan[++top]=(date){u,v,a[u],sz[v]};
fa[u]=v;sz[v]+=sz[u];a[u]=dep[x]^dep[y]^1;
return 0;
}
void del(int now){
while(top>now){
fa[zhan[top].x]=zhan[top].x;dep[zhan[top].x]=0;
a[zhan[top].x]=zhan[top].a;sz[zhan[top].y]=zhan[top].sz;
top--;
}
}
void solve(int x,int l,int r){
int mid=(l+r)>>1;int now=top;
for(int i=0;i<p[x].size();i++){
int ret=merge(p[x][i].u,p[x][i].v);
if(ret){for(int i=l;i<=r;i++)puts("No");del(now);return;}
}
if(l==r){puts("Yes");del(now);return;}
solve(lson,l,mid);solve(rson,mid+1,r);del(now);
}
int main(){
freopen("grape.in","r",stdin);
freopen("grape.out","w",stdout);
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=m;i++){
int u,v,l,r;scanf("%d%d%d%d",&u,&v,&l,&r);l++;
if(l>r) continue;
query(1,1,T,l,r,u,v);
}
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
solve(1,1,T);
return 0;
}
情报传递：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int N=1000050;
int head[N],to[N],nxt[N],cnt,n,rt,T;
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
struct data{
int type,x,y,tim,id;
}q[N];
bool cmp(const data &a,const data &b){
if(a.tim==b.tim) return a.type<b.type;
else return a.tim<b.tim;
}
int deep[N],size[N],son[N],dfn[N],tt,id[N],top[N],fa[N];
void dfs1(int x,int f){
size[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==f) continue;
deep[y]=deep[x]+1;dfs1(y,x);size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x,int f){
top[x]=f;dfn[x]=++tt;id[tt]=x;
if(son[x]) dfs2(son[x],f);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int tr[N*4];
/*void update(int x,int l,int r,int id){
if(l==r) {tr[x]=1;return;}
int mid=(l+r)>>1;
if(id<=mid) update(lson,l,mid,id);
else update(rson,mid+1,r,id);
tr[x]=tr[lson]+tr[rson];
}
int query(int x,int l,int r,int xl,int xr){
if(xl<=l&&r<=xr) return tr[x];
int mid=(l+r)>>1;
if(xr<=mid) return query(lson,l,mid,xl,xr);
else if(xl>mid) return query(rson,mid+1,r,xl,xr);
else return query(lson,l,mid,xl,mid)+query(rson,mid+1,r,mid+1,xr);
}*/
int lowbit(int x){return x&-x;}
void update(int x,int v){
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}
int query(int x){
int ret=0;
for(int i=x;i;i-=lowbit(i)) ret+=tr[i];
return ret;
}
struct date{
int x,y;
}ans[N];
date Lca(int x,int y){
int ret1=deep[x]+deep[y],ret2=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
//ret2+=query(1,1,n,dfn[top[x]],dfn[x]);
ret2+=query(dfn[x])-query(dfn[top[x]]-1);
x=fa[top[x]];
}
if(deep[x]<deep[y]) swap(x,y);
//ret2+=query(1,1,n,dfn[y],dfn[x]);
ret2+=query(dfn[x])-query(dfn[y]-1);
return (date){ret1-2*deep[y]+1,ret2};
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
if(!x) rt=i;
else lnk(i,x),fa[i]=x;
}
dfs1(rt,0);dfs2(rt,rt);scanf("%d",&T);int xh=0;
for(int i=1;i<=T;i++){
int type;scanf("%d",&type);
if(type==1){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);++xh;
q[i]=(data){1,x,y,i-z,xh};
}
else{
int x;scanf("%d",&x);
q[i]=(data){2,x,0,i,0};
}
}
sort(q+1,q+1+T,cmp);
for(int i=1;i<=T;i++){
if(q[i].type==2) update(dfn[q[i].x],1);//update(1,1,n,dfn[q[i].x]);
else ans[q[i].id]=Lca(q[i].x,q[i].y);
}
for(int i=1;i<=xh;i++) printf("%d %d
",ans[i].x,ans[i].y);
return 0;
}
消耗战：
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1000050;
int head[N],to[N],nxt[N],w[N],cnt,tt;
int h[N],t[N],nx[N],tmp,n,m,bj[N];
ll dp[N],val[N];
void lnk(int x,int y,int z){
to[++cnt]=y,nxt[cnt]=head[x],w[cnt]=z,head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],w[cnt]=z,head[y]=cnt;
}
void insert(int x,int y){
if(x==y) return;
t[++tmp]=y,nx[tmp]=h[x],h[x]=tmp;
t[++tmp]=x,nx[tmp]=h[y],h[y]=tmp;
}
int size[N],dfn[N],id[N],son[N],top[N],deep[N],fa[N],a[N],zhan[N];
void dfs1(int x,int f){
size[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==f) continue;
val[y]=min(val[x],1ll*w[i]);
deep[y]=deep[x]+1;dfs1(y,x);fa[y]=x;size[y]+=size[x];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x,int f){
dfn[x]=++tt;top[x]=f;id[tt]=x;
if(son[x]) dfs2(son[x],f);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int Lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(deep[x]<deep[y]) swap(x,y);
return y;
}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
void Dp(int x,int f){
ll res=0;dp[x]=val[x];
for(int i=h[x];i;i=nx[i]){
int y=t[i];if(y==f) continue;
Dp(y,x);res+=dp[y];
}
h[x]=0;
if(!res) dp[x]=val[x];
else if(!bj[x]&&res<dp[x]) dp[x]=res;
}
void solve(){
int k;scanf("%d",&k);tmp=0;
for(int i=1;i<=k;i++){scanf("%d",&a[i]);bj[a[i]]=1;}
sort(a+1,a+1+k,cmp);int tp=0;zhan[++tp]=1;
for(int i=1;i<=k;i++){
if(!tp){zhan[++tp]=a[i];continue;}
int p=Lca(zhan[tp],a[i]);
while(1){
if(deep[zhan[tp-1]]<=deep[p]){
insert(zhan[tp],p);tp--;
if(zhan[tp]!=p) zhan[++tp]=p;
break;
}
insert(zhan[tp],zhan[tp-1]);tp--;
}
zhan[++tp]=a[i];
}
while(tp>1) insert(zhan[tp],zhan[tp-1]),tp--;
Dp(1,1);printf("%lld
",dp[1]);
for(int i=1;i<=k;i++) bj[a[i]]=0;
}
int main(){
val[1]=1ll<<60;scanf("%d",&n);
for(int i=1;i<n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);lnk(x,y,z);}
dfs1(1,0);dfs2(1,1);scanf("%d",&m);
while(m--) solve();
return 0;
}
Peaks:
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
typedef long long ll;
const int N=400050;
int n,m,Q,sz,fa[N],rt[N],ls[N*20],rs[N*20],sum[N*20],hsh[N],Fa[N];
int id[N],dfn[N],ed[N],h[N],v[N],size[N],son[N],top[N];
struct data{
int a,b,c;
}e[500050];
bool cmp(const data &a,const data &b){return a.c<b.c;}
int head[N],to[N],nxt[N],cnt,tt,tot,res;
inline void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
}
inline int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
inline void dfs1(int x,int f){
size[x]=1;
for(RG int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=f){
Fa[y]=x;dfs1(y,x);size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
}
inline void dfs2(int x,int ff){
dfn[x]=++tot;id[tot]=x;top[x]=ff;
if(son[x]) dfs2(son[x],ff);
for(RG int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=Fa[x]&&y!=son[x]) dfs2(y,y);
}
ed[x]=tot;
}
inline void insert(RG int x,RG int &y,RG int l,RG int r,RG int u){
y=++sz;ls[y]=ls[x],rs[y]=rs[x];sum[y]=sum[x]+1;
if(l==r) return;
RG int mid=(l+r)>>1;
if(u<=mid) insert(ls[x],ls[y],l,mid,u);
else insert(rs[x],rs[y],mid+1,r,u);
}
inline int query(RG int x,RG int y,RG int l,RG int r,RG int k){
if(l==r) return l;
RG int mid=(l+r)>>1;
if(sum[ls[y]]-sum[ls[x]]>=k) return query(ls[x],ls[y],l,mid,k);
else return query(rs[x],rs[y],mid+1,r,k-(sum[ls[y]]-sum[ls[x]]));
}
inline int jump(RG int x,RG int lim){
RG int j=x;
while(x&&v[top[x]]<=lim){
j=top[x],x=Fa[top[x]];
}
if(v[x]>lim||v[top[x]]<=lim) return j;
RG int l=dfn[top[x]],r=dfn[x],ret=0;
while(l<=r){
RG int mid=(l+r)>>1;
if(v[id[mid]]<=lim) r=mid-1,ret=mid;
else l=mid+1;
}
return id[ret];
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
for(RG int i=1;i<=n;i++) scanf("%d",&h[i]),hsh[++res]=h[i];
for(RG int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+1+m,cmp);for(int i=1;i<=n;i++) fa[i]=i;tt=n;
for(RG int i=1;i<=m;i++){
RG int x=find(e[i].a),y=find(e[i].b);
if(y!=x){
tt++;v[tt]=e[i].c;fa[x]=fa[y]=tt;fa[tt]=tt;
lnk(tt,x);lnk(tt,y);
}
}
for(RG int i=1;i<=tt;i++){
RG int g=find(i);
if(!dfn[g]) dfs1(g,g),dfs2(g,g);
}
sort(hsh+1,hsh+res+1);res=unique(hsh+1,hsh+1+res)-hsh-1;
for(RG int i=1;i<=tot;i++){
rt[i]=rt[i-1];
if(id[i]<=n) insert(rt[i],rt[i],1,res,lower_bound(hsh+1,hsh+1+res,h[id[i]])-hsh);
}
RG int lastans=0;
while(Q--){
RG int u,x,k;scanf("%d%d%d",&u,&x,&k);
u^=lastans,x^=lastans,k^=lastans;
RG int Lca=jump(u,x);
if(sum[rt[ed[Lca]]]-sum[rt[dfn[Lca]-1]]<k) puts("-1"),lastans=0;
else lastans=query(rt[dfn[Lca]-1],rt[ed[Lca]],1,res,(sum[rt[ed[Lca]]]-sum[rt[dfn[Lca]-1]])-k+1),printf("%d
",hsh[lastans]),lastans=hsh[lastans];
}
return 0;
}
上帝与集合：
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100050;
ll bj[10000005],T;
bool vis[10000005];
ll qpow(ll x,ll y,ll mod){
ll ret=1;
while(y){
if(y&1) (ret*=x)%=mod;
(x*=x)%=mod;y>>=1;
}
return ret;
}
ll getphi(ll P){
ll M=P;ll res=P;
for(ll i=2;i*i<=P;i++)
if(res%i==0) {
(M/=i)*=i-1;
while(res%i==0) res/=i;
}
if(res>1) (M/=res)*=res-1;
return M;
}
ll solve(ll p){
if(vis[p]) return bj[p];
ll phi=getphi(p);vis[p]=1;
return bj[p]=qpow(2,solve(phi)+phi,p);
}
int main(){
scanf("%lld",&T);bj[1]=0;vis[1]=1;
while(T--){
ll p;scanf("%lld",&p);
printf("%lld
",solve(p));
}
return 0;
}
Savage:
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100050;
int P[N],C[N],l[N],n;
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void exgcd(int a,int b,int &x,int &y){
if(!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=(a/b)*x;
}
bool check(int i,int j,int M){
int a=P[i]-P[j],b=M,c=C[j]-C[i];
int Gcd=gcd(a,b);
if(c%Gcd) return 1;
int x,y;
a/=Gcd;b/=Gcd;c/=Gcd;
exgcd(a,b,x,y);b=abs(b);
x=((c*x)%b+b)%b;
if(!x) x+=b;
if(x>min(l[i],l[j])) return 1;
return 0;
}
bool judge(int M){
for(int i=1;i<=n;i++) if(M<C[i]) return 0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!check(i,j,M)){
return 0;
}
}
}
return 1;
}
int main(){
freopen("savage.in","r",stdin);
freopen("savage.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&C[i],&P[i],&l[i]);
}
for(int i=1;i<=1e6;i++){
if(judge(i)) {cout<<i<<endl;return 0;}
}
return 0;
}