var
a,b:int64;
begin
readln(a,b);
writeln(a+b);
end.Problem1000
#include<cstdio>
using namespace std;
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
return 0;
}Problem1000
#include<cstdio>
using namespace std;
int main()
{
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
Problem1000
#include<cstdio>
using namespace std;
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
return 0;
}Problem1000
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a + b << endl;
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}Problem1000
import java.util.*;
public class Main{
public static void main(String[] srgs){
Scanner jin=new Scanner(System.in);
int a=jin.nextInt();
int b=jin.nextInt();
int ans=a+b;
System.out.println(ans);
}
}Problem1000
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int a=cin.nextInt();
int b=cin.nextInt();
Add tmp=new Add();
int ans=tmp.add(a,b);
System.out.println(ans);
}
}
class Add{
int add(int x,int y){
return x+y;
}
}Problem1000
var a,b:integer;
begin
read(a,b);
writeln(a+b);
end.Problem1001
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int aa[7000000][3],o[2000000],A[1100][1100],B[1100][1100],C[1100][1100],q[10000000],hao[1100][1100][2],dist[2000000];
bool dl[2000000];
int n,m,i,j,num,tot,head,tail,S,T;
void add(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
void addedge(int p,int q,int v)
{
//printf("addedge: %d %d %d\n",p,q,v);
add(p,q,v);
add(q,p,v);
}
void pan()
{
if (n!=1&&m!=1) return;
int ans=99999999;
int x;
if (n==1&&m==1) printf("%d\n",0);
else if (n==1)
{
for (int i=1;i<m;i++)
{
scanf("%d",&x);
if (x<ans) ans=x;
}
printf("%d\n",ans);
}
else if (m==1)
{
for (int i=1;i<n;i++)
{
scanf("%d",&x);
if (x<ans) ans=x;
}
printf("%d\n",ans);
}
exit(0);
}
void init()
{
scanf("%d%d",&n,&m);
pan();
for (i=1;i<=n;i++)
for (j=1;j<m;j++) scanf("%d",&A[i][j]);
for (i=1;i<n;i++)
for (j=1;j<=m;j++) scanf("%d",&B[i][j]);
for (i=1;i<n;i++)
for (j=1;j<m;j++) scanf("%d",&C[i][j]);
num=0;
for (i=1;i<n;i++)
for (j=1;j<m;j++) hao[i][j][0]=++num,hao[i][j][1]=++num;
//for (i=1;i<n;i++){for (j=1;j<m;j++) printf(" %d %d ",hao[i][j][0],hao[i][j][1]);printf("\n");}
S=++num,T=++num;
for (i=1;i<n;i++)
for (j=1;j<m;j++)
{
addedge(hao[i][j][0],hao[i][j][1],C[i][j]);
if (i<n-1) addedge(hao[i][j][0],hao[i+1][j][1],A[i+1][j]);
if (j<m-1) addedge(hao[i][j][1],hao[i][j+1][0],B[i][j+1]);
}
for (i=1;i<n;i++)
{
addedge(S,hao[i][1][0],B[i][1]);
addedge(hao[i][m-1][1],T,B[i][m]);
}
for (j=1;j<m;j++)
{
addedge(S,hao[n-1][j][0],A[n][j]);
addedge(hao[1][j][1],T,A[1][j]);
}
}
bool relax(int x,int y,int v)
{
if (dist[y]>dist[x]+v)
{
dist[y]=dist[x]+v;
return 1;
}
return 0;
}
void doit()
{
head=tail=0;
memset(dist,127,sizeof(dist[0])*(T+10));
dist[S]=0;
q[++tail]=S;
dl[S]=1;
while (head!=tail)
{
++head;if (head==3000000) head=1;
int x=q[head];
int p=o[x];
dl[x]=0;
while (p)
{
int y=aa[p][1];
if (relax(x,y,aa[p][2]))
if (!dl[y])
{
//printf("y=%d\n",y);
++tail;if (tail==3000000) tail=1;
q[tail]=y;
dl[y]=1;
}
p=aa[p][0];
}
//printf("%d\n",tail);
}
printf("%d\n",dist[T]);
}
int main()
{
//freopen("10014.in","r",stdin);freopen("1.out","w",stdout);
init();
doit();
return 0;
}
Problem1002
#include<cstdio>
#include<cstring>
using namespace std;
int n;
struct number
{
int m[51],l;
void clear()
{
memset(m,0,sizeof(m));
l=1;
}
void out()
{
for (int i=l;i;i--) printf("%d",m[i]);
printf("\n");
}
friend number operator *(int x,number a)
{
int i;
for (i=1;i<=a.l;i++) a.m[i]*=x;
for (i=1;i<a.l;i++)
if (a.m[i]>9) a.m[i+1]+=a.m[i]/10,a.m[i]%=10;
while (a.m[a.l]>9)
a.m[a.l+1]=a.m[a.l]/10,a.m[a.l]%=10,a.l++;
return a;
}
friend number operator -(number a,number b)
{
int i;
for (i=1;i<=b.l;i++) a.m[i]-=b.m[i];
for (i=1;i<a.l;i++)
if (a.m[i]<0) a.m[i]+=10,a.m[i+1]--;
while (a.m[a.l]==0&&a.l>1) a.l--;
return a;
}
friend number operator +(number a,int x)
{
a.m[1]+=x;
int i;
for (i=1;i<a.l;i++)
if (a.m[i]>9) a.m[i+1]+=a.m[i]/10,a.m[i]%=10;
while (a.m[a.l]>9)
a.m[a.l+1]=a.m[a.l]/10,a.m[a.l]%=10,a.l++;
return a;
}
} f[111];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
f[1].l=1,f[1].m[1]=1;
f[2].l=1,f[2].m[1]=5;
for (int i=3;i<=n;i++)
f[i]=3*f[i-1]-f[i-2]+2;
f[n].out();
return 0;
}
Problem1002
#include<cstdio>
#include<cstring>
using namespace std;
int n;
struct number
{
int m[51],l;
void out()
{
for (int i=l;i;i--) printf("%d",m[i]);
printf("\n");
}
friend number operator *(int x,number a)
{
int i;
for (i=1;i<=a.l;i++) a.m[i]*=x;
for (i=1;i<a.l;i++)
if (a.m[i]>9) a.m[i+1]+=a.m[i]/10,a.m[i]%=10;
while (a.m[a.l]>9)
a.m[a.l+1]=a.m[a.l]/10,a.m[a.l]%=10,a.l++;
return a;
}
friend number operator -(number a,number b)
{
int i;
for (i=1;i<=b.l;i++) a.m[i]-=b.m[i];
for (i=1;i<a.l;i++)
if (a.m[i]<0) a.m[i]+=10,a.m[i+1]--;
while (a.m[a.l]==0&&a.l>1) a.l--;
return a;
}
friend number operator +(number a,int x)
{
a.m[1]+=x;
int i;
for (i=1;i<a.l;i++)
if (a.m[i]>9) a.m[i+1]+=a.m[i]/10,a.m[i]%=10;
while (a.m[a.l]>9)
a.m[a.l+1]=a.m[a.l]/10,a.m[a.l]%=10,a.l++;
return a;
}
} f[111];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
f[1].l=1,f[1].m[1]=1;
f[2].l=1,f[2].m[1]=5;
for (int i=3;i<=n;i++)
f[i]=3*f[i-1]-f[i-2]+2;
f[n].out();
return 0;
}
Problem1003
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 999999999
const int DD=105,NN=23;
int ban[DD][NN],q[1000],dist[NN],o[NN],aa[10000][3],cost[DD][DD],f[DD];
int n,m,D,K,tot=1;
bool flag[NN],dl[NN];
int spfa(int l,int r)
{
memset(flag,0,sizeof(flag));
int i,j,head=0,tail=1;
for (i=l;i<=r;i++)
for (j=1;j<=n;j++) if (ban[i][j]) flag[j]=true;
memset(dist,60,sizeof(dist));
dist[1]=0;
memset(dl,0,sizeof(dl));
dl[1]=true;
q[1]=1;
while (head<tail)
{
int x=q[++head],dd=dist[x];
dl[x]=false;
for (int p=o[x];p;p=aa[p][0])
{
int y=aa[p][1];
if (flag[y]) continue;
if (dist[y]>dd+aa[p][2])
{
dist[y]=dd+aa[p][2];
//printf("dis[y]=%d\n",dist[y]);
if (!dl[y]) dl[y]=true,q[++tail]=y;
}
}
}
//printf("dist[n]=%d\n",dist[n]);
if (dist[n]==dist[0]) return -1;
return dist[n];
}
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d",&D,&n,&K,&m);
int i,j,x,y,z,t;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z),addedge(y,x,z);
}
scanf("%d",&t);
for (i=1;i<=t;i++)
{
scanf("%d%d%d",&x,&y,&z);
for (j=y;j<=z;j++) ban[j][x]=true;
}
for (i=1;i<=D;i++)
for (j=i;j<=D;j++) cost[i][j]=(j-i+1)*spfa(i,j);//,printf("cost[%d][%d]=%d\n",i,j,cost[i][j]);
for (i=1;i<=D;i++)
{
f[i]=inf;
for (j=0;j<i;j++)
{
if (cost[j+1][i]<0) continue;
int tmp=j?f[j]+cost[j+1][i]+K:cost[j+1][i];
if (tmp<f[i]) f[i]=tmp;
}
}
printf("%d\n",f[D]);
return 0;
}Problem1004
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000][1000],f[100][100][100],sum[1000],b[1000];
int S1,S2,S3,m,mo,n,i,j,k,ans;
bool flag,ttt,vt[1000];
int ksm(int a,int b)
{
int res=1;
for (;b;b>>=1,a=a*a%mo) if (b&1) res=res*a%mo;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&S1,&S2,&S3,&m,&mo);
n=S1+S2+S3;
for (flag=false,i=1;i<=m;i++)
{
ttt=true;
for (j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]!=j) ttt=false;
}
if (ttt) flag=true;
}
if (!flag)
{
m++;
for (i=1;i<=n;i++) a[m][i]=i;
}
ans=0;
for (int t=1;t<=m;t++)
{
//printf("\n-------------------------------------------------------------\n");
memset(vt,0,sizeof(vt));
int num=0;
for (j=1;j<=n;j++)
if (!vt[j])
{
vt[j]=true;
int len=1;
int now=a[t][j];
while (now!=j)
{
len++;
vt[now]=true;
now=a[t][now];
}
b[++num]=len;
sum[num]=sum[num-1]+b[num];
}
//for (i=1;i<=num;i++) printf("%d ",b[i]);printf("\n");
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (i=1;i<=num;i++)
for (j=0;j<=S1;j++)
for (k=0;k<=S2;k++)
{
if (sum[i]<j+k) continue;
if (sum[i]-j-k>S3) continue;
if (b[i]<=j) f[i][j][k]+=f[i-1][j-b[i]][k];
if (b[i]<=k) f[i][j][k]+=f[i-1][j][k-b[i]];
if (b[i]<=sum[i]-j-k) f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mo;
//printf("%d\n",f[i][j][k]);
}
ans=(ans+f[num][S1][S2])%mo;
}
//printf("m=%d\n",m);
ans=ans*ksm(m,mo-2)%mo;
printf("%d\n",ans);
return 0;
}
Problem1004
#include<stdio.h>
#include<string.h>
int a[1000][1000],f[100][100][100],sum[1000],b[1000];
int S1,S2,S3,m,mo,n,i,j,k,ans;
int flag,ttt,vt[1000];
int ksm(int a,int b)
{
int res=1;
for (;b;b>>=1,a=a*a%mo) if (b&1) res=res*a%mo;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&S1,&S2,&S3,&m,&mo);
n=S1+S2+S3;
for (flag=0,i=1;i<=m;i++)
{
ttt=1;
for (j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]!=j) ttt=0;
}
if (ttt) flag=1;
}
if (!flag)
{
m++;
for (i=1;i<=n;i++) a[m][i]=i;
}
ans=0;
int t;
for (t=1;t<=m;t++)
{
//printf("\n-------------------------------------------------------------\n");
memset(vt,0,sizeof(vt));
int num=0;
for (j=1;j<=n;j++)
if (!vt[j])
{
vt[j]=1;
int len=1;
int now=a[t][j];
while (now!=j)
{
len++;
vt[now]=1;
now=a[t][now];
}
b[++num]=len;
sum[num]=sum[num-1]+b[num];
}
//for (i=1;i<=num;i++) printf("%d ",b[i]);printf("\n");
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (i=1;i<=num;i++)
for (j=0;j<=S1;j++)
for (k=0;k<=S2;k++)
{
if (sum[i]<j+k) continue;
if (sum[i]-j-k>S3) continue;
if (b[i]<=j) f[i][j][k]+=f[i-1][j-b[i]][k];
if (b[i]<=k) f[i][j][k]+=f[i-1][j][k-b[i]];
if (b[i]<=sum[i]-j-k) f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mo;
//printf("%d\n",f[i][j][k]);
}
ans=(ans+f[num][S1][S2])%mo;
}
//printf("m=%d\n",m);
ans=ans*ksm(m,mo-2)%mo;
printf("%d\n",ans);
return 0;
}
Problem1004
#include<cstdio>
#include<cstring>
using namespace std;
#define ln printf("\n")
const int NN=105;
int a[NN][NN],f[NN][NN][NN],b[NN],vt[NN],num[NN];
int n,S1,S2,S3,m,P;
int ksm(int a,int b,int c)
{
int res=1;
for (;b;b>>=1,a=a*a%c)
if (b&1) res=res*a%c;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&S1,&S2,&S3,&m,&P);
n=S1+S2+S3;
bool flag=false;
int i,j,k;
for (i=1;i<=m;i++)
{
bool tt=true;
for (j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]!=j) tt=false;
}
if (tt) flag=true;
}
if (!flag)
{
m++;
for (i=1;i<=n;i++) a[m][i]=i;
}
int ans=0;
for (int ii=1;ii<=m;ii++)
{
//printf("\n-------------------------------------------------------------------------------\n");
for (i=1;i<=n;i++) b[i]=a[ii][i];
memset(vt,0,sizeof(vt));
int cnt=0;
for (i=1;i<=n;i++) if (!vt[i])
{
vt[i]=true;
int x=b[i];
num[++cnt]=1;
for (;x!=i;x=b[x]) num[cnt]++,vt[x]=true;
}
//for (i=1;i<=cnt;i++) printf("%d ",num[i]);ln;
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (i=1;i<=cnt;i++)
for (j=0;j<=S1;j++)
for (k=0;k<=S2;k++)
{
int &res=f[i][j][k];
if (j>=num[i]) res+=f[i-1][j-num[i]][k];
if (k>=num[i]) res+=f[i-1][j][k-num[i]];
if (n-j-k>=num[i]) res+=f[i-1][j][k];
res%=P;
}
ans+=f[n][S1][S2];
if (ans>P) ans-=P;
//printf("ans=%d\n",ans);
}
ans=ans*ksm(m,P-2,P)%P;
//ln;ln;
printf("%d\n",ans);
return 0;
}Problem1004
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000][1000],f[100][100][100],sum[1000],b[1000];
int S1,S2,S3,m,mo,n,i,j,k,ans;
bool flag,ttt,vt[1000];
int ksm(int a,int b)
{
int res=1;
for (;b;b>>=1,a=a*a%mo) if (b&1) res=res*a%mo;
return res;
}
int main()
{
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&S1,&S2,&S3,&m,&mo);
n=S1+S2+S3;
for (flag=false,i=1;i<=m;i++)
{
ttt=true;
for (j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]!=j) ttt=false;
}
if (ttt) flag=true;
}
if (!flag)//²»ÐýתҲÊÇÒ»ÖÖÖû»
{
m++;
for (i=1;i<=n;i++) a[m][i]=i;
}
ans=0;
for (int t=1;t<=m;t++)
{
memset(vt,0,sizeof(vt));
int num=0;
for (j=1;j<=n;j++)
if (!vt[j])
{
vt[j]=true;
int len=1;
int now=a[t][j];
while (now!=j)
{
len++;
vt[now]=true;
now=a[t][now];
}
b[++num]=len;
sum[num]=sum[num-1]+b[num];
}
memset(f,0,sizeof(f));
f[0][0][0]=1;//f[i][j][k]±íʾÒѾ·ÅÍêÁËÇ°i¸öÑ»·£¬ÓÃÁËj¸öA£¬k¸öB
for (i=1;i<=num;i++)
for (j=0;j<=S1;j++)
for (k=0;k<=S2;k++)
{
if (b[i]<=j) f[i][j][k]+=f[i-1][j-b[i]][k];
if (b[i]<=k) f[i][j][k]+=f[i-1][j][k-b[i]];
if (b[i]<=sum[i]-j-k) f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mo;
}
ans=(ans+f[num][S1][S2])%mo;
}
ans=ans*ksm(m,mo-2)%mo;//Õâ¸öÌâû·¨ÔÚÇóºÍµÄ¹ý³ÌÖÐÈ¡Ä££¬ËùÒÔ×îºóÓÃÄæÔªÇó¡£
printf("%d\n",ans);
return 0;
}Problem1004
#include<cstdio>
#include<cstring>
using namespace std;
#define ln printf("\n")
int n,m,P,S1,S2,S3,a[1011][1011];
int calc(int *a)
{
static bool vt[1011];
static int num[1011],sum[1011],f[111][111][111];
int i,j,k,cnt=0;
memset(vt,0,sizeof(vt));
//for (i=1;i<=n;i++) printf("%d ",a[i]);ln;
for (i=1;i<=n;i++) if (!vt[i])
{
int x=i,len=0;
while (!vt[x]) vt[x]=true,len++,x=a[x];
num[++cnt]=len;
sum[cnt]=sum[cnt-1]+len;
}
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (i=1;i<=cnt;i++)
for (j=0;j<=S1;j++)
for (k=0;k<=S2;k++)
{
int &res=f[i][j][k];
if (j>=num[i]) res+=f[i-1][j-num[i]][k];
if (k>=num[i]) res+=f[i-1][j][k-num[i]];
if (sum[i]-j-k>=num[i]) res+=f[i-1][j][k];
res%=P;
}
return f[cnt][S1][S2];
}
int ksm(int a,int b,int c)
{
int res=1;
for (a%=c;b;b>>=1,a=a*a%c)
if (b&1) res=res*a%c;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&S1,&S2,&S3,&m,&P);
n=S1+S2+S3;
bool flag=false;
int i,j;
for (i=1;i<=m;i++)
{
bool tt=true;
for (j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]!=j) tt=false;
}
if (tt) flag=true;
}
if (!flag)
{
m++;
for (j=1;j<=n;j++) a[m][j]=j;
}
int ans=0;
for (i=1;i<=m;i++)
ans=(ans+calc(a[i]))%P;
ans=ans*ksm(m,P-2,P)%P;
printf("%d\n",ans);
return 0;
}Problem1005
#include<cstdio>
#include<cstring>
using namespace std;
const int NN=1011;
int pr[NN],num[NN],du[NN];
int n,cnt,sum,tot;
bool is[NN];
struct big
{
int m[3000],l;
big() {memset(m,0,sizeof(m));l=1;}
void out() {for (int i=l;i;i--) printf("%d",m[i]);printf("\n");}
void update()
{
for (int i=1;i<l;i++)
if (m[i]>9) m[i+1]+=m[i]/10,m[i]%=10;
while (m[l]>9)
m[l+1]=m[l]/10,m[l]%=10,l++;
}
friend big operator *(int x,big a)
{
for (int i=1;i<=a.l;i++) a.m[i]*=x;
a.update();
return a;
}
} ans;
void shai()
{
memset(is,1,sizeof(is));
is[1]=false;
for (int i=2;i<=n;i++)
{
if (is[i]) pr[++tot]=i;
for (int j=1;j<=tot;j++)
{
int x=i*pr[j];
if (x>n) break;
is[x]=false;
if (i%pr[j]==0) break;
}
}
}
void add(int k,int t)
{
for (int i=1;i<=tot;i++)
{
int x=k;
while (x>1)
{
num[i]+=x/pr[i]*t;
x/=pr[i];
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,j,x;
if (n==1)
{
scanf("%d",&x);
printf(x==0?"1\n":"0\n");
return 0;
}
for (i=1;i<=n;i++)
{
scanf("%d",&du[i]);
if (du[i]==0) {printf("0\n");return 0;}
else if (du[i]==-1) cnt++;
else sum+=du[i]-1;
}
if (sum>n-2) {printf("0\n");return 0;}
shai();
//for (i=1;i<=tot;i++) printf("%d ",pr[i]);printf("\n");
add(n-2,1);
add(n-2-sum,-1);
for (i=1;i<=n;i++)
if (du[i]>0) add(du[i]-1,-1);
//for (i=1;i<=tot;i++) printf("%d ",num[i]);printf("\n");
ans.m[1]=1;
for (i=1;i<=tot;i++)
for (j=1;j<=num[i];j++) ans=pr[i]*ans;
//printf("cnt=%d\n",cnt);
for (i=1;i<=n-2-sum;i++) ans=cnt*ans;
ans.out();
return 0;
}
Problem1006
#include<cstdio>
#include<queue>
using namespace std;
const int NN=10011,MM=1001111;
int o[NN],aa[MM*2][2],pos[NN],label[NN];
int n,m,tot=1;
bool vt[NN];
struct ppt
{
int num,v;
ppt(int a=0,int b=0) {num=a,v=b;}
friend bool operator <(ppt a,ppt b) {return a.num<b.num;}
};
priority_queue<ppt> Q;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);
}
for (i=1;i<=n;i++) Q.push(ppt(0,i));
for (i=n;i;i--)
{
while (vt[Q.top().v]) Q.pop();
int v=Q.top().v;
Q.pop();
pos[v]=i;
vt[v]=true;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y]) Q.push(ppt(++label[y],y));
}
}
int ans=0;
for (i=1;i<=n;i++)
{
int t=1;
for (int p=o[i];p;p=aa[p][0])
{
int y=aa[p][1];
if (pos[y]>pos[i]) t++;
}
if (t>ans) ans=t;
}
printf("%d\n",ans);
return 0;
}Problem1006
#include<cstdio>
#include<queue>
using namespace std;
const int NN=10011,MM=1001111;
int o[NN],aa[MM*2][2],pos[NN],label[NN];
int n,m,tot=1;
bool vt[NN];
struct ppt
{
int num,v;
ppt(int a=0,int b=0) {num=a,v=b;}
friend bool operator <(ppt a,ppt b) {return a.num<b.num;}
};
priority_queue<ppt> Q;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);
}
for (i=1;i<=n;i++) Q.push(ppt(0,i));
for (i=n;i;i--)
{
while (vt[Q.top().v]) Q.pop();
int v=Q.top().v;Q.pop();
vt[v]=true;
pos[v]=i;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y]) Q.push(ppt(++label[y],y));
}
}
int ans=0;
for (i=1;i<=n;i++)
{
int t=1;
for (int p=o[i];p;p=aa[p][0])
{
int y=aa[p][1];
if (pos[y]>pos[i]) t++;
}
if (t>ans) ans=t;
}
printf("%d\n",ans);
return 0;
}Problem1007
#include<cstdio>
#include<algorithm>
using namespace std;
#define DD double
#define sm 0.00000001
int n,i,num,top,sta[510000];
struct zhixian {DD k,b;int id;} a[510000],b[510000];
struct point {DD x,y;};
bool cmp(zhixian a,zhixian b) {return a.k<b.k;}
point calc(int i,int j)
{
//printf("calc: %d %d\n",i,j);
point tmp;
tmp.x=(a[i].b-a[j].b)/(a[j].k-a[i].k);
tmp.y=tmp.x*a[i].k+a[i].b;
//printf("calc tmp: %.3f %.3f\n",tmp.x,tmp.y);
return tmp;
}
bool check(int i,int j,int k)
{
point t1,t2;
t1=calc(i,j);
//printf("t1: %.3f %.3f\n",t1.x,t1.y);
t2=calc(i,k);
//printf("t2: %.3f %.3f\n",t2.x,t2.y);
if (t2.x-t1.x<sm) return 1;
else return 0;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lf%lf",&a[i].k,&a[i].b),a[i].id=i,b[i]=a[i];
sort(b+1,b+n+1,cmp);
//for (i=1;i<=n;i++) printf("%.0f %.0f %d\n",b[i].k,b[i].b,b[i].id);
num=1;
for (i=2;i<=n;i++)
if (b[i].k!=b[num].k) b[++num]=b[i];
else if (b[num].b<b[i].b) b[num]=b[i];
//for (i=1;i<=num;i++) printf("%d\n",b[i].id);
for (i=1;i<=num;i++)
{
//printf("\n--------------------------------------\n");
while (top>1&&check(sta[top-1],sta[top],b[i].id)) --top;
sta[++top]=b[i].id;
}
sort(sta+1,sta+top+1);
for (i=1;i<=top;i++) printf("%d ",sta[i]);
return 0;
}
Problem1007
#include<cstdio>
#include<algorithm>
using namespace std;
#define DD double
#define sm 0.00000001
int n,i,num,top,sta[510000];
struct zhixian {DD k,b;int id;} a[510000],b[510000];
struct point {DD x,y;};
bool cmp(zhixian a,zhixian b) {return a.k<b.k;}
point calc(int i,int j)
{
point tmp;
tmp.x=(a[i].b-a[j].b)/(a[j].k-a[i].k);
tmp.y=tmp.x*a[i].k+a[i].b;
return tmp;
}
bool check(int i,int j,int k)
{
point t1,t2;
t1=calc(i,j);
t2=calc(i,k);
if (t2.x-t1.x<sm) return 1;
else return 0;
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%lf%lf",&a[i].k,&a[i].b),a[i].id=i,b[i]=a[i];
sort(b+1,b+n+1,cmp);
num=1;
for (i=2;i<=n;i++)
if (b[i].k!=b[num].k) b[++num]=b[i];
else if (b[num].b<b[i].b) b[num]=b[i];
for (i=1;i<=num;i++)
{
while (top>1&&check(sta[top-1],sta[top],b[i].id)) --top;
sta[++top]=b[i].id;
}
sort(sta+1,sta+top+1);
for (i=1;i<=top;i++) printf("%d ",sta[i]);
return 0;
}
Problem1008
#include<cstdio>
using namespace std;
#define LL long long
const int mo=100003;
LL n,m,ans;
LL ksm(LL a,LL b)
{
LL res=1;
for (a%=mo;b;b>>=1,a=a*a%mo) if (b&1) res=res*a%mo;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%lld%lld",&m,&n);
LL ans=(ksm(m,n)-m*ksm(m-1,n-1))%mo;
if (ans<0) ans+=mo;
printf("%lld\n",ans);
return 0;
}
Problem1009
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,mo,i,j,k,next[22],res;
char s[22];
struct matrix{int a[22][22];matrix(){memset(a,0,sizeof(a));}} sum,ans;
matrix mul(matrix A,matrix B)
{
matrix C;
int i,j,k;
for (k=0;k<m;k++)
for (i=0;i<m;i++)
for (j=0;j<m;j++) C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%mo;
return C;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d\n",&n,&m,&mo);
scanf("%s",s+1);
next[1]=0;
for (i=2,j=0;i<=m;i++)
{
while (s[i]!=s[j+1]&&j>0) j=next[j];
if (s[i]==s[j+1]) j++;
next[i]=j;
}
for (i=0;i<m;i++)
for (j=0;j<=9;j++)
{
k=i;
while (k>0&&s[k+1]-'0'!=j) k=next[k];
if (s[k+1]-'0'==j) ++k;
++sum.a[i][k];
}
for (i=0;i<m;i++) ans.a[i][i]=1;
while (n>0)
{
if (n&1) ans=mul(ans,sum);
n>>=1;
sum=mul(sum,sum);
}
res=0;
for (i=0;i<m;i++) res=(res+ans.a[0][i])%mo;
printf("%d\n",res);
return 0;
}
Problem1009
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,mo,i,j,k,next[22],res;
char s[22];
struct matrix{int w[22][22];matrix(){memset(w,0,sizeof(w));}} sum,ans;
matrix mul(matrix A,matrix B)
{
matrix C;
int i,j,k;
for (k=0;k<m;k++)
for (i=0;i<m;i++)
for (j=0;j<m;j++) C.w[i][j]=(C.w[i][j]+A.w[i][k]*B.w[k][j])%mo;
return C;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d\n",&n,&m,&mo);
scanf("%s",s+1);
next[1]=0;
for (i=2,j=0;i<=m;i++)
{
while (s[i]!=s[j+1]&&j>0) j=next[j];
if (s[i]==s[j+1]) j++;
next[i]=j;
}
for (i=0;i<m;i++)
for (j=0;j<=9;j++)
{
k=i;
while (k>0&&s[k+1]-'0'!=j) k=next[k];
if (s[k+1]-'0'==j) ++k;
++sum.w[i][k];
}
for (i=0;i<m;i++) ans.w[i][i]=1;
while (n>0)
{
if (n&1) ans=mul(ans,sum);
n>>=1;
sum=mul(sum,sum);
}
res=0;
for (i=0;i<m;i++) res=(res+ans.w[0][i])%mo;
printf("%d\n",res);
return 0;
}
Problem1010
#include<cstdio>
using namespace std;
#define LL long long
int n,head,tail,k,j,i,q[51000];
LL L,f[51000],b[51000],S[51000];
LL fenzi(int i) {return f[i]+b[i]*b[i]+2*(L+1)*b[i];}
int main()
{
/*
f[i]:前i个玩具装完的最小费用
f[i]=min(f[j]+cost[j+1][i]
cost[i][j]=(j-i+S[j]-S[i-1]-L)^2
*/
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%lld",&n,&L);
for (i=1;i<=n;i++) scanf("%lld",&S[i]),S[i]+=S[i-1],b[i]=i+S[i];
head=0;
q[tail=1]=0;
for (i=1;i<=n;i++)
{
int k=q[head+2],j=q[head+1];
while (fenzi(k)-fenzi(j)<=(b[k]-b[j])*2*(i+S[i])&&tail>head+1)
{
++head;
k=q[head+2],j=q[head+1];
}
f[i]=f[j]+(b[i]-b[j]-(L+1))*(b[i]-b[j]-(L+1));
k=q[tail],j=q[tail-1];
while ((fenzi(i)-fenzi(k))*(b[k]-b[j])<=(fenzi(k)-fenzi(j))*(b[i]-b[k])&&tail>head+1)
{
--tail;
k=q[tail],j=q[tail-1];
}
q[++tail]=i;
}
printf("%lld\n",f[n]);
return 0;
}
Problem1011
#include<cstdio>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
typedef double DD;
const DD eps=1e-7;
const int NN=101111;
int a[NN],n;
DD alfa,f[NN],sum[NN];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%lf",&n,&alfa);
int i,j;
for (i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
int t=mii(n,2000);
for (i=1;i<=t;i++)
for (j=1;j<i;j++)
if (j-alfa*i<eps) f[i]+=(DD)a[i]*a[j]/(i-j);
for (i=2001;i<=n;i++)
{
int k=(int)(alfa*i);
DD t=(k+1)*0.5;
f[i]=(DD)a[i]*sum[k]/(i-t);
}
for (i=1;i<=n;i++) printf("%.6f\n",f[i]);
return 0;
}Problem1011
#include<cstdio>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
typedef double DD;
const DD eps=1e-7;
const int NN=101111;
int a[NN],n;
DD alfa,f[NN],sum[NN];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%lf",&n,&alfa);
int i,j;
for (i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
int t=mii(n,1000);
for (i=1;i<=t;i++)
for (j=1;j<i;j++)
if (j-alfa*i<eps) f[i]+=(DD)a[i]*a[j]/(i-j);
else break;
for (i=1001;i<=n;i++)
{
int k=(int)(alfa*i);
DD t=(k+1)*0.5;
f[i]=(DD)a[i]*sum[k]/(i-t);
}
for (i=1;i<=n;i++) printf("%.6f\n",f[i]);
return 0;
}Problem1011
#include<cstdio>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
typedef double DD;
const DD eps=1e-7;
const int NN=100005;
int a[NN],n;
DD alfa,f[NN],sum[NN];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%lf",&n,&alfa);
int i,j;
for (i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
int t=mii(n,900);
for (i=1;i<=t;i++)
for (j=1;j<i;j++)
if (j-alfa*i<eps) f[i]+=(DD)a[i]*a[j]/(i-j);
else break;
for (i=901;i<=n;i++)
{
int k=(int)(alfa*i);
DD t=(k+1)*0.5;
f[i]=(DD)a[i]*sum[k]/(i-t);
}
for (i=1;i<=n;i++) printf("%.6f\n",f[i]);
return 0;
}Problem1012
#include<cstdio>
using namespace std;
const int NN=200011;
int m,D,n,lastans,top;
struct ppt
{
int w,id;
} s[NN];
int cha(int x)
{
int l=1,r=top,res;
while (l<=r)
{
int mid=(l+r)>>1;
if (s[mid].id>=x) res=s[mid].w,r=mid-1;
else l=mid+1;
}
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d\n",&m,&D);
n=0;
lastans=0;
int i,x;
for (i=1;i<=m;i++)
{
char ch=getchar();
if (ch=='A')
{
scanf("%d\n",&x);
x=(x+lastans)%D;
while (top&&x>s[top].w) top--;
top++;
s[top].w=x,s[top].id=++n;
}
else
{
scanf("%d\n",&x);
x=cha(n-x+1);
printf("%d\n",lastans=x);
}
}
return 0;
}Problem1013
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double DD;
const int NN=13;
DD a[NN][NN],X[NN],b[NN],c[NN];
int n;
void gause()
{
int i,j;
for (i=1;i<n;i++)
{
DD tmp=fabs(a[i][i]);
int mj=i;
for (j=i+1;j<=n;j++)
if (fabs(a[j][i])>tmp) tmp=fabs(a[j][i]),mj=j;
if (mj!=i) for (j=i;j<=n+1;j++) swap(a[i][j],a[mj][j]);
for (j=i+1;j<=n;j++)
{
DD tmp=a[j][i]/a[i][i];
for (int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*tmp;
}
}
X[n]=a[n][n+1]/a[n][n];
for (i=n-1;i;i--)
{
DD tmp=0;
for (j=i+1;j<=n;j++) tmp+=X[j]*a[i][j];
X[i]=(a[i][n+1]-tmp)/a[i][i];
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
DD tmp=0;
int i,j;
for (i=1;i<=n;i++)
{
scanf("%lf",&b[i]);
tmp+=b[i]*b[i];
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++) scanf("%lf",&c[j]);
for (j=1;j<=n;j++) a[i][j]=-2*c[j]+2*b[j];
for (j=1;j<=n;j++) a[i][n+1]-=c[j]*c[j];
a[i][n+1]+=tmp;
}
gause();
for (i=1;i<=n;i++) printf(i==n?"%.3f\n":"%.3f ",X[i]);
return 0;
}Problem1014
#include<cstdio>
#include<cstring>
using namespace std;
#define pp 19980723
const int NN=101111;
int fa[NN],son[NN][2],size[NN],key[NN],h[NN],mi[NN],s[NN];
int n,m,TTT,root;
char ss[NN];
void update(int t)
{
int x=son[t][0],y=son[t][1];
size[t]=size[x]+size[y]+1;
h[t]=h[x]*mi[size[y]+1]+key[t]*mi[size[y]]+h[y];
}
void rotate(int t,int p)
{
int y=fa[t];
if (fa[y])
{
if (y==son[fa[y]][0]) son[fa[y]][0]=t;
else son[fa[y]][1]=t;
}
fa[t]=fa[y];
son[y][p^1]=son[t][p];
if (son[t][p]) fa[son[t][p]]=y;
son[t][p]=y;
fa[y]=t;
update(y),update(t);
}
void splay(int t,int ff)
{
while (fa[t]!=ff)
{
int y=fa[t];
if (fa[y]==ff)
if (t==son[y][0]) rotate(t,1);
else rotate(t,0);
else
if (y==son[fa[y]][0])
if (t==son[y][0]) rotate(y,1),rotate(t,1);
else rotate(t,0),rotate(t,1);
else
if (t==son[y][1]) rotate(y,0),rotate(t,0);
else rotate(t,1),rotate(t,0);
}
update(t);
if (!ff) root=t;
}
int find(int x)
{
int t=root;
for (;;)
{
int tmp=size[son[t][0]];
if (x==tmp+1) return t;
if (x<=tmp) t=son[t][0];
else x-=(tmp+1),t=son[t][1];
}
}
int gethash(int l,int r)
{
l++,r++;
int x=find(l-1);splay(x,0);
int y=find(r+1);splay(y,x);
x=son[y][0];
return h[x];
}
int build(int l,int r)
{
int v=++TTT;
int mid=(l+r)>>1;
size[v]=1;
key[v]=h[v]=s[mid];
if (l<mid) son[v][0]=build(l,mid-1),fa[son[v][0]]=v;
if (r>mid) son[v][1]=build(mid+1,r),fa[son[v][1]]=v;
update(v);
return v;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
mi[0]=1;
int i,x,y;
for (i=1;i<=100000;i++) mi[i]=mi[i-1]*pp;
scanf("%s",ss+1);
n=strlen(ss+1);
s[1]=0;
for (i=1;i<=n;i++) s[i+1]=ss[i];
s[n+2]=0;
root=build(1,n+2);
scanf("%d",&m);
for (i=1;i<=m;i++)
{
char ch=getchar();
while (ch!='Q'&&ch!='R'&&ch!='I') ch=getchar();
if (ch=='Q')
{
scanf("%d%d",&x,&y);
if (x>y) {int t=x;x=y;y=t;}
int l=0,r=n-y+1,res=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (gethash(x,x+mid-1)==gethash(y,y+mid-1)) res=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",res);
}
else if (ch=='R')
{
scanf("%d",&x);
ch=getchar();
while (ch<'a'||ch>'z') ch=getchar();
x=find(x+1);
key[x]=h[x]=ch;
splay(x,0);
}
else
{
scanf("%d",&x);
ch=getchar();
while (ch<'a'||ch>'z') ch=getchar();
y=find(x+2),x=find(x+1);
splay(x,0);
splay(y,x);
son[y][0]=++TTT;
fa[TTT]=y;
key[TTT]=h[TTT]=ch;
size[TTT]=1;
splay(TTT,0);
n++;
}
}
return 0;
}Problem1015
#include<cstdio>
using namespace std;
const int NN=4001111,MM=2001111;
int fa[NN],size[NN],aa[MM*2][2],del[NN],o[NN],ans[NN];
int n,m,K,tot=1;
bool flag[NN];
int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=n;i++) fa[i]=i,size[i]=1;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
addedge(x,y),addedge(y,x);
}
scanf("%d",&K);
for (i=1;i<=K;i++)
{
scanf("%d",&x);x++;
del[i]=x;
flag[x]=true;
}
int now=n-K;
for (i=1;i<=n;i++)
if (!flag[i])
for (int p=o[i];p;p=aa[p][0])
{
int y=aa[p][1];
if (flag[y]) continue;
int t1=getfa(i),t2=getfa(y);
if (t1==t2) continue;
now--;
if (size[t1]<size[t2]) fa[t1]=t2,size[t2]+=size[t1];
else fa[t2]=t1,size[t1]+=size[t2];
}
for (i=K;i;i--)
{
ans[i]=now++;
flag[del[i]]=false;
for (int p=o[del[i]];p;p=aa[p][0])
{
int y=aa[p][1];
if (flag[y]) continue;
int t1=getfa(del[i]),t2=getfa(y);
if (t1==t2) continue;
now--;
if (size[t1]<size[t2]) fa[t1]=t2,size[t2]+=size[t1];
else fa[t2]=t1,size[t1]+=size[t2];
}
}
printf("%d\n",now);
for (i=1;i<=K;i++) printf("%d\n",ans[i]);
return 0;
}
Problem1016
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mo 31011
#define NN 1100
int K[NN][NN],fa[NN],pos[NN],which[NN];
int n,m,i,j,k,x,y,ans;
bool use[100000],vt[10000];
struct edge {int a,b,w;} e[100000];
bool cmp (edge a,edge b) {return a.w<b.w;}
int getroot(int x) {return fa[x]==x?x:fa[x]=getroot(fa[x]);}
void gaosixiaoyuan(int n)
{
int i,j,k;
//for (i=1;i<=n;i++){for (j=1;j<=n;j++) printf("%d ",K[i][j]);printf("\n");}
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
while (K[j][i])
{
int tmp=K[i][i]/K[j][i];
for (k=i;k<=n;k++) K[i][k]=(K[i][k]-tmp*K[j][k])%mo;
for (k=i;k<=n;k++) tmp=K[i][k],K[i][k]=K[j][k],K[j][k]=tmp;
ans*=-1;
}
ans=ans*K[i][i]%mo;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e+1,e+m+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
int x=e[i].a,y=e[i].b;
if (getroot(x)==getroot(y)) continue;
use[i]=true;
fa[getroot(x)]=y;
}
ans=1;
for (i=1;i<=m;i=j+1)
{
for (j=i;e[j].w==e[i].w;j++);
j--;
for (k=1;k<=n;k++) fa[k]=k;
for (k=1;k<i;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
for (k=j+1;k<=m;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
memset(vt,0,sizeof(vt[0])*(n+10));
int cnt=0;
for (k=1;k<=n;k++)
{
int x=getroot(k);
if (!vt[x])
{
vt[x]=true;
pos[x]=++cnt;
which[cnt]=x;
}
}
memset(K,0,sizeof(K));
for (k=i;k<=j;k++)
{
int x=getroot(e[k].a),y=getroot(e[k].b);
if (x==y) continue;
x=pos[x],y=pos[y];
K[x][x]++,K[y][y]++;
K[x][y]--,K[y][x]--;
}
gaosixiaoyuan(cnt-1);
}
printf("%d\n",(ans%mo+mo)%mo);
}
Problem1016
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mo 31011
#define NN 1005
#define MM 1005
int K[NN][NN],fa[NN],pos[NN],which[NN];
int n,m,i,j,k,x,y,ans;
bool use[MM],vt[NN];
struct edge {int a,b,w;} e[MM];
bool cmp (edge a,edge b) {return a.w<b.w;}
int getroot(int x) {return fa[x]==x?x:fa[x]=getroot(fa[x]);}
void gaosixiaoyuan(int n)
{
int i,j,k;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
while (K[j][i])
{
int tmp=K[i][i]/K[j][i];
for (k=i;k<=n;k++) K[i][k]=(K[i][k]-tmp*K[j][k])%mo;
for (k=i;k<=n;k++) tmp=K[i][k],K[i][k]=K[j][k],K[j][k]=tmp;
ans*=-1;
}
ans=ans*K[i][i]%mo;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e+1,e+m+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
int x=e[i].a,y=e[i].b;
if (getroot(x)==getroot(y)) continue;
use[i]=true;
fa[getroot(x)]=y;
}
ans=1;
for (i=1;i<=m;i=j+1)
{
for (j=i;e[j].w==e[i].w;j++);
j--;
for (k=1;k<=n;k++) fa[k]=k;
for (k=1;k<i;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
for (k=j+1;k<=m;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
memset(vt,0,sizeof(vt[0])*(n+10));
int cnt=0;
for (k=1;k<=n;k++)
{
int x=getroot(k);
if (!vt[x])
{
vt[x]=true;
pos[x]=++cnt;
which[cnt]=x;
}
}
memset(K,0,sizeof(K));
for (k=i;k<=j;k++)
{
int x=getroot(e[k].a),y=getroot(e[k].b);
if (x==y) continue;
x=pos[x],y=pos[y];
K[x][x]++,K[y][y]++;
K[x][y]--,K[y][x]--;
}
gaosixiaoyuan(cnt-1);
}
printf("%d\n",(ans%mo+mo)%mo);
}
Problem1016
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mo 31011
#define NN 110
#define MM 1005
int K[NN][NN],fa[NN],pos[NN],which[NN];
int n,m,i,j,k,x,y,ans;
bool use[MM],vt[NN];
struct edge {int a,b,w;} e[MM];
bool cmp (edge a,edge b) {return a.w<b.w;}
int getroot(int x) {return fa[x]==x?x:fa[x]=getroot(fa[x]);}
void gaosixiaoyuan(int n)
{
int i,j,k;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
while (K[j][i])
{
int tmp=K[i][i]/K[j][i];
for (k=i;k<=n;k++) K[i][k]=(K[i][k]-tmp*K[j][k])%mo;
for (k=i;k<=n;k++) tmp=K[i][k],K[i][k]=K[j][k],K[j][k]=tmp;
ans*=-1;
}
ans=ans*K[i][i]%mo;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e+1,e+m+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
int x=e[i].a,y=e[i].b;
if (getroot(x)==getroot(y)) continue;
use[i]=true;
fa[getroot(x)]=y;
}
ans=1;
for (i=1;i<=m;i=j+1)
{
for (j=i;e[j].w==e[i].w;j++);
j--;
for (k=1;k<=n;k++) fa[k]=k;
for (k=1;k<i;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
for (k=j+1;k<=m;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
memset(vt,0,sizeof(vt[0])*(n+10));
int cnt=0;
for (k=1;k<=n;k++)
{
int x=getroot(k);
if (!vt[x])
{
vt[x]=true;
pos[x]=++cnt;
which[cnt]=x;
}
}
memset(K,0,sizeof(K));
for (k=i;k<=j;k++)
{
int x=getroot(e[k].a),y=getroot(e[k].b);
if (x==y) continue;
x=pos[x],y=pos[y];
K[x][x]++,K[y][y]++;
K[x][y]--,K[y][x]--;
}
gaosixiaoyuan(cnt-1);
}
printf("%d\n",(ans%mo+mo)%mo);
}
Problem1016
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mo 31011
#define NN 105
#define MM 1005
int K[NN][NN],fa[NN],pos[NN],which[NN];
int n,m,i,j,k,x,y,ans;
bool use[MM],vt[NN];
struct edge {int a,b,w;} e[MM];
bool cmp (edge a,edge b) {return a.w<b.w;}
int getroot(int x) {return fa[x]==x?x:fa[x]=getroot(fa[x]);}
void gaosixiaoyuan(int n)
{
int i,j,k;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
while (K[j][i])
{
int tmp=K[i][i]/K[j][i];
for (k=i;k<=n;k++) K[i][k]=(K[i][k]-tmp*K[j][k])%mo;
for (k=i;k<=n;k++) tmp=K[i][k],K[i][k]=K[j][k],K[j][k]=tmp;
ans*=-1;
}
ans=ans*K[i][i]%mo;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e+1,e+m+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
int x=e[i].a,y=e[i].b;
if (getroot(x)==getroot(y)) continue;
use[i]=true;
fa[getroot(x)]=y;
}
ans=1;
for (i=1;i<=m;i=j+1)
{
for (j=i;e[j].w==e[i].w;j++);
j--;
for (k=1;k<=n;k++) fa[k]=k;
for (k=1;k<i;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
for (k=j+1;k<=m;k++)
if (use[k]) fa[getroot(e[k].a)]=e[k].b;
memset(vt,0,sizeof(vt[0])*(n+5));
int cnt=0;
for (k=1;k<=n;k++)
{
int x=getroot(k);
if (!vt[x])
{
vt[x]=true;
pos[x]=++cnt;
which[cnt]=x;
}
}
memset(K,0,sizeof(K));
for (k=i;k<=j;k++)
{
int x=getroot(e[k].a),y=getroot(e[k].b);
if (x==y) continue;
x=pos[x],y=pos[y];
K[x][x]++,K[y][y]++;
K[x][y]--,K[y][x]--;
}
gaosixiaoyuan(cnt-1);
}
printf("%d\n",(ans%mo+mo)%mo);
}
Problem1016
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mo 31011
#define NN 111
#define MM 1111
int a[NN][NN],fa[NN],pos[NN];
int n,m,ans;
bool vt[NN],use[MM];
struct edge
{
int a,b,w;
friend bool operator < (edge x,edge y) {return x.w<y.w;}
} e[MM];
void gause(int (*a)[NN],int n)
{
int i,j,k,t;
for (i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
while (a[j][i])
{
for (k=i;k<=n;k++) swap(a[i][k],a[j][k]);
t=a[j][i]/a[i][i];
for (k=i;k<=n;k++) a[j][k]=(a[j][k]-t*a[i][k])%mo;
ans=-ans;
}
ans=ans*a[i][i]%mo;
}
}
int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,x,y,l,r,cnt;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e+1,e+m+1);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
x=getfa(e[i].a),y=getfa(e[i].b);
if (x==y) continue;
fa[x]=y;
use[i]=true;
}
//for (i=1;i<=n;i++) printf("%d ",use[i]);printf("\n");
ans=1;
for (l=1;l<=m;l=r+1)
{
for (r=l;e[r].w==e[l].w&&r<=m;r++);
r--;
for (i=1;i<=n;i++) fa[i]=i,vt[i]=false;
for (i=1;i<l;i++)
if (use[i]) fa[getfa(e[i].a)]=e[i].b;
for (i=r+1;i<=m;i++)
if (use[i]) fa[getfa(e[i].a)]=e[i].b;
//for (i=1;i<=n;i++) printf("%d ",getfa(i));printf("\n");
for (i=1;i<=n;i++) vt[getfa(i)]=true;
for (cnt=0,i=1;i<=n;i++)
if (vt[i]) pos[i]=++cnt;
memset(a,0,sizeof(a));
for (i=l;i<=r;i++)
{
x=getfa(e[i].a),y=getfa(e[i].b);
if (x==y) continue;
x=pos[x],y=pos[y];
a[x][x]++,a[y][y]++;
a[x][y]--,a[y][x]--;
}
//for (int i=1;i<=cnt;i++){for (int j=1;j<=cnt;j++)printf("%d ",a[i][j]);printf("\n");}printf("\n");
gause(a,cnt-1);
}
printf("%d\n",(ans%mo+mo)%mo);
return 0;
}
Problem1016
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mo 31011
#define ln printf("\n")
const int NN=105,MM=1005;
int n,m,a[NN][NN],fa[NN],pos[NN];
bool use[MM],vt[NN];
struct edge
{
int u,v,w;
void in() {scanf("%d%d%d",&u,&v,&w);}
friend bool operator <(edge a,edge b) {return a.w<b.w;}
} e[MM];
int gause(int n)
{
int res=1;
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++) while (a[j][i])
{
int t=a[i][i]/a[j][i];
for (int k=i;k<=n;k++) a[i][k]=(a[i][k]-t*a[j][k])%mo;
for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);
res=-res;
}
res=res*a[i][i]%mo;
}
return res;
}
int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main()
{
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++) e[i].in();
sort(e+1,e+m+1);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
int x=getfa(e[i].u),y=getfa(e[i].v);
if (x==y) continue;
use[i]=true;
fa[x]=y;
}
int ans=1,l,r;
for (l=1;l<=m;l=r+1)
{
for (r=l;r<=m&&e[r].w==e[l].w;r++);r--;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<l;i++)
if (use[i]) fa[getfa(e[i].u)]=e[i].v;
for (i=m;i>r;i--)
if (use[i]) fa[getfa(e[i].u)]=e[i].v;
memset(vt,0,sizeof(vt));
for (i=1;i<=n;i++) vt[getfa(i)]=true;
int cnt=0;
for (i=1;i<=n;i++) if (vt[i]) pos[i]=++cnt;
memset(a,0,sizeof(a));
for (i=l;i<=r;i++)
{
int x=getfa(e[i].u),y=getfa(e[i].v);
if (x==y) continue;
x=pos[x],y=pos[y];
a[x][x]++,a[y][y]++;
a[x][y]--,a[y][x]--;
}
ans=ans*gause(cnt-1)%mo;
}
printf("%d\n",(ans%mo+mo)%mo);
return 0;
}Problem1017
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define inf 999999999
const int NN=55;
int f[NN][105][2005],g[NN][105][2005],o[NN],w[NN],limit[NN],cost[NN],aa[NN][3];
int n,m,tot=1,ans;
bool vt[NN];
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
void dp(int v)
{
//printf("dp %d\n",v);
vt[v]=true;
int i,j,k,l;
if (o[v]==0)
{
limit[v]=min(limit[v],m/cost[v]);
for (j=0;j<=limit[v];j++)
for (k=j;k<=limit[v];k++)
f[v][j][k*cost[v]]=(k-j)*w[v];
return;
}
limit[v]=inf;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
dp(y);
limit[v]=min(limit[v],limit[y]/aa[p][2]);
}
memset(g,128,sizeof(g));
//printf("limit[%d]=%d\n",v,limit[v]);
for (j=0;j<=limit[v];j++) g[0][j][0]=0;
i=0;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1],need=aa[p][2];
//printf("y=%d\n",y);
i++;
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=0;l<=k;l++)
if (g[i-1][j][k-l]>=0&&f[y][j*need][l]>=0)
g[i][j][k]=max(g[i][j][k],g[i-1][j][k-l]+f[y][j*need][l]);
}
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=j;l<=limit[v];l++)
if (g[i][l][k]>=0)
{
f[v][j][k]=max(f[v][j][k],g[i][l][k]+(l-j)*w[v]);
ans=max(ans,f[v][j][k]);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y,z,j;
for (i=1;i<=n;i++)
{
scanf("%d",&w[i]);
char ch=getchar();ch=getchar();
//printf("ch=%c\n",ch);
if (ch=='A')
{
scanf("%d",&x);
for (j=1;j<=x;j++)
{
scanf("%d%d",&y,&z);
addedge(i,y,z);
}
}
else scanf("%d%d",&cost[i],&limit[i]);
}
memset(f,128,sizeof(f));
for (i=1;i<=n;i++) if (!vt[i]) dp(i);
printf("%d\n",ans);
return 0;
}Problem1017
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define inf 999999999
const int NN=55;
int f[NN][105][2005],g[NN][105][2005],o[NN],w[NN],limit[NN],cost[NN],aa[NN][3];
int n,m,tot=1,ans;
bool vt[NN];
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
void dp(int v)
{
//printf("dp %d\n",v);
vt[v]=true;
int i,j,k,l;
if (o[v]==0)
{
limit[v]=min(limit[v],m/cost[v]);
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=j;l<=limit[v];l++)
if (l*cost[v]<=k)
{
f[v][j][k]=(l-j)*w[v];
ans=max(ans,f[v][j][k]);
}
return;
}
limit[v]=inf;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
dp(y);
limit[v]=min(limit[v],limit[y]/aa[p][2]);
}
memset(g,128,sizeof(g));
//printf("limit[%d]=%d\n",v,limit[v]);
for (j=0;j<=limit[v];j++) g[0][j][0]=0;
i=0;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1],need=aa[p][2];
//printf("y=%d\n",y);
i++;
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=0;l<=k;l++)
if (g[i-1][j][k-l]>=0&&f[y][j*need][l]>=0)
g[i][j][k]=max(g[i][j][k],g[i-1][j][k-l]+f[y][j*need][l]);
}
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=j;l<=limit[v];l++)
if (g[i][l][k]>=0)
{
f[v][j][k]=max(f[v][j][k],g[i][l][k]+(l-j)*w[v]);
ans=max(ans,f[v][j][k]);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y,z,j;
for (i=1;i<=n;i++)
{
scanf("%d",&w[i]);
char ch=getchar();ch=getchar();
//printf("ch=%c\n",ch);
if (ch=='A')
{
scanf("%d",&x);
for (j=1;j<=x;j++)
{
scanf("%d%d",&y,&z);
addedge(i,y,z);
}
}
else scanf("%d%d",&cost[i],&limit[i]);
}
memset(f,128,sizeof(f));
for (i=1;i<=n;i++) if (!vt[i]) dp(i);
printf("%d\n",ans);
return 0;
}Problem1017
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define inf 999999999
const int NN=55;
int f[NN][105][2005],g[105][2005],o[NN],w[NN],limit[NN],cost[NN],aa[NN][3];
int n,m,tot=1,ans;
bool vt[NN];
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
void dp(int v)
{
vt[v]=true;
int i,j,k,l;
if (o[v]==0)
{
limit[v]=min(limit[v],m/cost[v]);
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=j;l<=limit[v];l++)
if (l*cost[v]<=k)
{
f[v][j][k]=(l-j)*w[v];
ans=max(ans,f[v][j][k]);
}
return;
}
limit[v]=inf;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
dp(y);
limit[v]=min(limit[v],limit[y]/aa[p][2]);
}
memset(g,128,sizeof(g));
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++) g[j][k]=0;
i=0;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1],need=aa[p][2];
i++;
for (j=0;j<=limit[v];j++)
for (k=m;k>=0;k--)
{
if (f[y][j][0]>=0) g[j][k]=g[j][k]+f[y][j][0];
else g[j][k]=-inf;
for (l=1;l<=k;l++)
if (g[j][k-l]>=0&&f[y][j*need][l]>=0)
g[j][k]=max(g[j][k],g[j][k-l]+f[y][j*need][l]);
}
}
for (j=0;j<=limit[v];j++)
for (k=0;k<=m;k++)
for (l=j;l<=limit[v];l++)
if (g[l][k]>=0)
{
f[v][j][k]=max(f[v][j][k],g[l][k]+(l-j)*w[v]);
ans=max(ans,f[v][j][k]);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y,z,j;
for (i=1;i<=n;i++)
{
scanf("%d",&w[i]);
char ch=getchar();ch=getchar();
if (ch=='A')
{
scanf("%d",&x);
for (j=1;j<=x;j++)
{
scanf("%d%d",&y,&z);
addedge(i,y,z);
}
}
else scanf("%d%d",&cost[i],&limit[i]);
}
memset(f,128,sizeof(f));
for (i=1;i<=n;i++) if (!vt[i]) dp(i);
printf("%d\n",ans);
return 0;
}Problem1018
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 111111
using namespace std;
struct DAT
{
bool v[2],s[2],x[2];
void prt() {printf("s:%d %d\nx:%d %d\nv:%d %d\n\n",s[0],s[1],x[0],x[1],v[0],v[1]);}
}dat[N<<2];
bool a[N][2][2];
int n,r1,r2,c1,c2;
int dx[3]={-1,0,1};
int dy[3]={0,1,0};
inline void build(int u,int l,int r)
{
if(l==r) {dat[u].s[0]=dat[u].s[1]=true;return;}
int mid=(l+r)>>1;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
}
inline void pack(DAT &u,DAT &ls,DAT &rs,int mid)
{
u.x[0]=ls.x[0]||(ls.s[0]&&a[mid][0][0]&&rs.x[0]&&a[mid][1][0]&&ls.s[1]);//左上-右上
u.x[1]=rs.x[1]||(rs.s[0]&&a[mid][0][0]&&ls.x[1]&&a[mid][1][0]&&rs.s[1]);//左下-右下
u.s[0]=(ls.s[0]&&a[mid][0][0]&&rs.s[0])||(ls.v[0]&&a[mid][1][0]&&rs.v[1]);//左上-左下
u.s[1]=(ls.s[1]&&a[mid][1][0]&&rs.s[1])||(ls.v[1]&&a[mid][0][0]&&rs.v[0]);//右上-右下
u.v[0]=(ls.s[0]&&a[mid][0][0]&&rs.v[0])||(ls.v[0]&&a[mid][1][0]&&rs.s[1]);//左上-右下
u.v[1]=(ls.s[1]&&a[mid][1][0]&&rs.v[1])||(ls.v[1]&&a[mid][0][0]&&rs.s[0]);//右上-左下
}
inline void updata(int u,int l,int r,int p)
{
if(l==r)
{
dat[u].x[0]=dat[u].x[1]=dat[u].v[1]=dat[u].v[0]=a[p][0][1];
dat[u].s[0]=dat[u].s[1]=true;
return;
}
int mid=(l+r)>>1;
if(p<=mid) updata(u<<1,l,mid,p);
else updata(u<<1|1,mid+1,r,p);
pack(dat[u],dat[u<<1],dat[u<<1|1],mid);
}
inline void change(bool pd)
{
if(r1>r2) swap(r1,r2),swap(c1,c2);
int dir;
for(int i=0;i<3;i++)
if(c1+dx[i]==c2&&r1+dy[i]==r2) dir=i;
if(dir==0) a[c2][r2][0]=pd,updata(1,1,n,c2);
else if(dir==1) a[c1][0][1]=pd,updata(1,1,n,c1);
else a[c1][r1][0]=pd,updata(1,1,n,c1);
}
inline void getpack(DAT &p,int u,int L,int R,int l,int r)
{
if(l<=L&&r>=R) {p=dat[u];return;}
int MID=(L+R)>>1;
if(r<=MID) getpack(p,u<<1,L,MID,l,r);
else if(l>=MID+1) getpack(p,u<<1|1,MID+1,R,l,r);
else
{
DAT tmp1,tmp2;
getpack(tmp1,u<<1,L,MID,l,MID);
getpack(tmp2,u<<1|1,MID+1,R,MID+1,r);
pack(p,tmp1,tmp2,MID);
}
}
inline void getans()
{
if(c1>c2) swap(c1,c2),swap(r1,r2);
DAT pa,pb,pc;
getpack(pa,1,1,n,1,c1);
getpack(pb,1,1,n,c1,c2);
getpack(pc,1,1,n,c2,n);
if(r1==r2)
{
if(r1==0)
{
if(pb.s[0]||(pa.x[1]&&pb.v[1])||(pc.x[0]&&pb.v[0])||(pa.x[1]&&pb.s[1]&&pc.x[0])) puts("Y");
else puts("N");
}
else
{
if(pb.s[1]||(pa.x[1]&&pb.v[0])||(pc.x[0]&&pb.v[1])||(pa.x[1]&&pb.s[0]&&pc.x[0])) puts("Y");
else puts("N");
}
}
else
{
if(r1==0)
{
if(pb.v[0]||(pa.x[1]&&pb.s[1])||(pc.x[0]&&pb.s[0])) puts("Y");
else puts("N");
}
else
{
if(pb.v[1]||(pa.x[1]&&pb.s[0])||(pc.x[0]&&pb.s[1])) puts("Y");
else puts("N");
}
}
}
inline void go()
{
char str[10];
scanf("%d",&n);
build(1,1,n);
while(scanf("%s",str))
{
if(str[0]=='E') break;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
r1--; r2--;
if(str[0]=='O') change(1);
else if(str[0]=='C') change(0);
else getans();
}
}
int main()
{
go();
return 0;
}Problem1019
#include<cstdio>
using namespace std;
typedef long long LL;
int n;
LL f[33][3],g[33][3];
bool vt[101];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d\n",&n);
int i;
for (i=1;i<=6;i++)
{
char s[3];
scanf("%s",s+1);
int x=s[1]-'A',y=s[2]-'A';
if (vt[x]) continue;
vt[x]=true;
g[1][x]=y,f[1][x]=1;
}
for (i=2;i<=n;i++) for (int x=0;x<3;x++)
{
int y=g[i-1][x];
int z=3-x-y;
if (g[i-1][y]==z)
{
g[i][x]=z;
f[i][x]=f[i-1][x]+1+f[i-1][y];
}
else
{
g[i][x]=y;
f[i][x]=f[i-1][x]+1+f[i-1][y]+1+f[i-1][x];
}
}
printf("%lld\n",f[n][0]);
return 0;
}Problem1020
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-5
#define MAXN 30
#define MAXM 40
#define MAXQ 1000000
using namespace std;
int dcmp(double p)
{
if(fabs(p)<eps) return 0;
return p>eps?1:-1;
}
int n,m;
double ans;
struct Point
{
double x,y;
Point() {}
Point(double x,double y): x(x),y(y) {}
friend Point operator + (const Point &a,const Point &b){ return Point(a.x+b.x,a.y+b.y); }
friend Point operator - (const Point &a,const Point &b){ return Point(a.x-b.x,a.y-b.y); }
friend Point operator * (const Point &a,double p){ return Point(a.x*p,a.y*p); }
friend Point operator / (const Point &a,double p){ return Point(a.x/p,a.y/p); }
friend bool operator == (const Point &a,const Point &b){ return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y); }
void Read(){ scanf("%lf %lf",&x,&y); }
}temp[MAXN];
typedef Point Vector;
double Dot(const Vector &a,const Vector &b){ return a.x*b.x+a.y*b.y; }
double Len(const Vector &a){ return sqrt(Dot(a,a)); }
double Cross(const Vector &a,const Vector &b){ return a.x*b.y-a.y*b.x; }
Vector Normal(const Vector &a){ return Vector(-a.y,a.x); }
bool On(const Point &a,const Point &b,const Point &c)
{ return !dcmp(Cross(b-a,c-a))&&dcmp((a.x-b.x)*(a.x-c.x))<=0&&dcmp((a.y-b.y)*(a.y-c.y))<=0; }
bool inter(const Point &a,const Point &b,const Point &c,const Point &d)
{ return dcmp(Cross(c-a,b-a)*Cross(d-a,b-a))<=0&&dcmp(Cross(a-c,d-c)*Cross(b-c,d-c))<=0; }
Point getinter(const Point &a,const Vector &b,const Point &c,const Vector &d)
{
Vector u=a-c;
double t=Cross(d,u)/Cross(b,d);
return a+b*t;
}
struct Seg
{
Point a,b;
Seg() {}
Seg(const Point &a,const Point &b): a(a),b(b) {}
}queue[1000010];
struct Polygon
{
Point p[MAXM];
int tot;
bool In(Point &point)
{
int total=0;
for(int i=1;i<=tot;i++)
if(On(point,p[i],p[i%tot+1]))
return true;
Point Ray=Point(-10001,point.y+0.1);
point.y+=0.1;
for(int i=1;i<=tot;i++)
total=total+inter(Ray,point,p[i],p[i%tot+1]);
point.y-=0.1;
return total&1;
}
}island[MAXN];
struct near
{
Point P;
double dis;
near() {}
near(const Point &a,double b): P(a),dis(b) {}
};
near DISPS(const Point &a,const Point &b,const Point &c)
{
if(b==c) return near(b,Len(b-a));
Vector v1=c-b,v2=a-b,v3=a-c;
if(dcmp(Dot(v1,v2))<=0) return near(b,Len(v2));
if(dcmp(Dot(v1,v3))>=0) return near(c,Len(v3));
Vector v=Normal(b-c);
Point ans=getinter(a,v,b,v1);
return near(ans,Len(a-ans));
}
bool check(Point &p)
{
for(int i=1;i<=n;i++)
if(island[i].In(p))
return true;
return false;
}
near Find(Point &p)
{
if(check(p)) return near(p,0);
near ans1;
ans1.dis=1<<30;
for(int i=1;i<=n;i++)
for(int j=1;j<=island[i].tot;j++)
{
near get=DISPS(p,island[i].p[j],island[i].p[j%island[i].tot+1]);
if(dcmp(ans1.dis-get.dis)>=0) ans1=get;
}
ans=max(ans,ans1.dis);
return ans1;
}
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) temp[i].Read();
for(int i=1;i<=n;i++)
{
scanf("%d",&island[i].tot);
for(int j=1;j<=island[i].tot;j++)
island[i].p[j].Read();
}
}
void search()
{
int front=0,rear=0;
for(int i=1;i<m;i++)
queue[++rear]=Seg(temp[i],temp[i+1]);
Seg head;
while(front!=rear)
{
head=queue[front=front%MAXQ+1];
Point p1=Find(head.a).P,p2=Find(head.b).P,l=head.a,r=head.b,mid=(l+r)/2;
while(!(l==r))
{
Point mid=(r+l)/2;
if(Len(mid-p1)<Len(mid-p2)) l=mid;
else r=mid;
}
double nowans=Len(l-p1);
if(nowans-ans>eps) queue[rear=rear%MAXQ+1]=Seg(head.a,mid),queue[rear=rear%MAXQ+1]=Seg(mid,head.b);
}
}
int main()
{
read();
search();
printf("%.2lf\n",ans);
return 0;
}Problem1022
#include<cstdio>
using namespace std;
int tc,n,ans,i,x;
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
for (scanf("%d",&tc);tc;tc--)
{
scanf("%d",&n);
bool flag=false;
for (ans=0,i=1;i<=n;i++)
{
scanf("%d",&x),ans^=x;
if (x>1) flag=true;
}
if ((ans>0&&flag)||(ans==0&&!flag)) printf("John\n");
else printf("Brother\n");
}
return 0;
}Problem1022
#include<stdio.h>
int tc,n,ans,i,x;
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
for (scanf("%d",&tc);tc;tc--)
{
scanf("%d",&n);
int flag=0;
for (ans=0,i=1;i<=n;i++)
{
scanf("%d",&x),ans^=x;
if (x>1) flag=1;
}
if ((ans>0&&flag)||(ans==0&&!flag)) printf("John\n");
else printf("Brother\n");
}
return 0;
}Problem1022
#include<cstdio>
using namespace std;
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int tes;
for (scanf("%d",&tes);tes;tes--)
{
int ans=0,x,n;
scanf("%d",&n);
bool flag=false;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
ans^=x;
if (x>1) flag=true;
}
if ((ans==0&&!flag)||(ans>0&&flag)) printf("John\n");
else printf("Brother\n");
}
return 0;
}
Problem1022
#include<cstdio>
using namespace std;
int main()
{
int tes;
for (scanf("%d",&tes);tes;tes--)
{
int ans=0,x,n;
scanf("%d",&n);
bool flag=false;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
ans^=x;
if (x>1) flag=true;
}
if ((ans==0&&!flag)||(ans>0&&flag)) printf("John\n");
else printf("Brother\n");
}
return 0;
}
Problem1022
#include<cstdio>
using namespace std;
int tes,n;
int main()
{
for (scanf("%d",&tes);tes;tes--)
{
scanf("%d",&n);
int xorsum=0,i,x;
bool flag=false;
for (i=1;i<=n;i++)
{
scanf("%d",&x);
xorsum^=x;
if (x>1) flag=true;
}
if ((xorsum==0&&!flag)||(xorsum!=0&&flag)) printf("John\n");
else printf("Brother\n");
}
return 0;
}Problem1022
import java.util.*;
public class Main{
public static void main(String[] srgs){
Scanner cin=new Scanner(System.in);
int tes=cin.nextInt();
for (;tes>0;tes--){
int n=cin.nextInt();
int xorsum=0,i,x;
boolean flag=false;
for (i=1;i<=n;i++){
x=cin.nextInt();
xorsum^=x;
if (x>1) flag=true;
}
if ((xorsum==0&&!flag)||(xorsum!=0&&flag)) System.out.println("John\r");
else System.out.println("Brother\r");
}
}
}Problem1023
#include<cstdio>
using namespace std;
#define NN 510000
int dfn[NN],low[NN],aa[NN*2][2],o[NN],fa[NN],from[NN],b[NN],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}
Problem1023
#include<cstdio>
using namespace std;
#define NN 51000*2
int dfn[NN],low[NN],aa[NN*2][2],o[NN],fa[NN],from[NN],b[NN],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}
Problem1023
#include<cstdio>
using namespace std;
#define NN 51000
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN*2];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}
Problem1023
#include<cstdio>
using namespace std;
#define NN 51000
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN*2];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
using namespace std;
#define NN 51000
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN*2];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
//if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
using namespace std;
#define NN 51000
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN*2];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
//if (p==(from[v]^1)) continue;
if (low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
using namespace std;
#define NN 51000
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
struct ppt {int w,id;} q[NN*2];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void dp_on_circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=max(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
void dfs(int v)
{
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (p==(from[v]^1)) continue;
if (dfn[y]) low[v]=min(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=min(low[v],low[y]);
}
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
//if (p==(from[v]^1)) continue;
if (low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
else if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
dp_on_circle();
for (int i=1;i<b[0];i++) f[v]=max(f[v],f[b[i]]+min(i,b[0]-i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x);
addedge(x,last);
last=x;
}
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",f[i]);printf("\n");
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
using namespace std;
#define NN 51111
#define mii(a,b) ((a)<(b)?(a):(b))
#define maa(a,b) ((a)>(b)?(a):(b))
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
bool vt[NN];
struct ppt
{
int w,id;
ppt(int a=0,int b=0) {w=a,id=b;}
} q[NN*2];
void circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=maa(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}
/*void circle()
{
int head=0,tail=0,i;
//f[i]+f[j]+i-j
for (i=1;i<=b[0];i++) b[i+b[0]]=b[i];
for (i=1;i<b[0]*2;i++)
{
while (head<tail&&q[head+1].id<i-b[0]/2) head++;
ans=maa(ans,q[head+1].w+f[b[i]]+i);
while (head<tail&&q[tail].w<f[b[i]]-i) tail--;
q[++tail]=ppt(f[b[i]]-i,i);
}
}*/
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
int p,y,x;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (vt[y]) low[v]=mii(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=mii(low[v],low[y]);
}
}
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (low[y]>dfn[v])
{
ans=maa(ans,f[v]+f[y]+1);
f[v]=maa(f[v],f[y]+1);
}
else if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
circle();
for (int i=1;i<b[0];i++) f[v]=maa(f[v],f[b[i]]+mii(i,b[0]-i));
}
}
}
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (tot=1,i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x),addedge(x,last);
last=x;
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
using namespace std;
#define NN 51111
#define mii(a,b) ((a)<(b)?(a):(b))
#define maa(a,b) ((a)>(b)?(a):(b))
int dfn[NN],low[NN],aa[10000000][2],o[NN],fa[NN],from[NN],b[NN*2],f[NN];
int n,tot=1,ans,TIME,m;
bool vt[NN];
struct ppt
{
int w,id;
ppt(int a=0,int b=0) {w=a,id=b;}
} q[NN*2];
/*void circle()
{
int head=0,tail=1,i;
for (i=1;i<b[0];i++) b[i+b[0]]=b[i];
q[1].id=1,q[1].w=f[b[1]]-1;
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&i-q[head+1].id>b[0]/2) head++;
ans=maa(ans,q[head+1].w+i+f[b[i]]);
while (head<tail&&f[b[i]]-i>q[tail].w) tail--;
tail++;
q[tail].w=f[b[i]]-i,q[tail].id=i;
}
}*/
void circle()
{
int head=0,tail=1,i;
q[1]=ppt(f[b[1]]-1,1);
//f[i]+f[j]+i-j
for (i=1;i<=b[0];i++) b[i+b[0]]=b[i];
for (i=2;i<b[0]*2;i++)
{
while (head<tail&&q[head+1].id<i-b[0]/2) head++;
ans=maa(ans,q[head+1].w+f[b[i]]+i);
while (head<tail&&q[tail].w<f[b[i]]-i) tail--;
q[++tail]=ppt(f[b[i]]-i,i);
}
}
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
int p,y,x;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (vt[y]) low[v]=mii(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=mii(low[v],low[y]);
}
}
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (low[y]>dfn[v])
{
ans=maa(ans,f[v]+f[y]+1);
f[v]=maa(f[v],f[y]+1);
}
else if (p!=from[y]&&dfn[v]<dfn[y])
{
b[0]=0;
for (x=y;x!=fa[v];x=fa[x]) b[++b[0]]=x;
circle();
for (int i=1;i<b[0];i++) f[v]=maa(f[v],f[b[i]]+mii(i,b[0]-i));
}
}
}
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (tot=1,i=1;i<=m;i++)
{
scanf("%d",&k);
scanf("%d",&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x),addedge(x,last);
last=x;
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}Problem1023
#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
#define ln printf("\n")
#define mp make_pair
#define fi first
#define se second
const int NN=50111,MM=200111;
int o[NN],aa[MM<<1][2],f[NN],dfn[NN],low[NN],from[NN],fa[NN],b[NN<<1];
int n,m,num,ans,TIME,tot=1;
bool vt[NN];
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
inline void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
void dp_circle()
{
//printf("\n----------------------------------------------------------------------\n");
static pii que[NN<<1];
int i;
for (i=1;i<=num;i++) b[i+num]=b[i];
int head=0,tail=1;
que[1]=mp(1,f[b[1]]-1);
//for(i=1;i<=num;i++)printf("%d %d ",b[i],f[b[i]]);ln;
for (i=2;i<=num*2;i++)
{
while (head<tail&&i-que[head+1].fi>(num>>1)) head++;
if (head<tail) ans=max(ans,f[b[i]]+i+que[head+1].se);
//if (ans==12) printf("i=%d que[head+1].fi=%d que[head+1].se=%d\n",i,que[head+1].fi,que[head+1].se);
while (head<tail&&f[b[i]]-i>=que[tail].se) tail--;
que[++tail]=mp(i,f[b[i]]-i);
}
}
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if ((p^1)==from[v]) continue;
if (!vt[y])
{
fa[y]=v;
from[y]=p;
dfs(y);
low[v]=min(low[v],low[y]);
}
else low[v]=min(low[v],dfn[y]);
}
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if ((p^1)==from[v]) continue;
if (p==from[y]&&low[y]>dfn[v])
{
ans=max(ans,f[v]+f[y]+1);
f[v]=max(f[v],f[y]+1);
}
else if (p!=from[y]&&dfn[v]<dfn[y])
{
num=0;
for (int x=y;x!=fa[v];x=fa[x]) b[++num]=x;
//printf("b ");for (int i=1;i<=num;i++) printf("%d ",b[i]);ln;
dp_circle();
for (int i=1;i<num;i++)
f[v]=max(f[v],f[b[i]]+min(num-i,i));
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,k,last,j,x;
for (i=1;i<=m;i++)
{
scanf("%d%d",&k,&last);
for (j=2;j<=k;j++)
{
scanf("%d",&x);
addedge(last,x),addedge(x,last);
last=x;
}
}
dfs(1);
//printf("f ");for (i=1;i<=n;i++) printf("%d ",f[i]);ln;
printf("%d\n",ans);
return 0;
}Problem1024
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 999999999
typedef double DD;
DD dfs(DD n,DD m,int K)
{
if (K==1)
{
if (n<m) {DD t=n;n=m;m=t;}
return n/m;
}
DD res=inf;
for (int i=1;i+i<=K;i++)
{
DD x=(DD)i/K*n,y=(DD)i/K*m;
DD tmp=max(dfs(x,m,i),dfs(n-x,m,K-i));
if (tmp<res) res=tmp;
tmp=max(dfs(n,y,i),dfs(n,m-y,K-i));
if (tmp<res) res=tmp;
}
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int n,m,K;
scanf("%d%d%d",&n,&m,&K);
printf("%.6f\n",dfs(n,m,K));
return 0;
}Problem1025
#include<cstdio>
using namespace std;
typedef long long LL;
#define ln printf("\n")
const int NN=1005;
int pr[NN];
int n,prcnt;
LL f[NN][NN];
void shai()
{
static bool vt[NN];
vt[1]=true;
for (int i=2;i<=n;i++)
{
if (!vt[i]) pr[++prcnt]=i;
for (int j=1;j<=prcnt;j++)
{
int x=i*pr[j];
if (x>n) break;
vt[x]=true;
if (i%pr[j]==0) break;
}
}
//printf("pr ");for (int i=1;i<=prcnt;i++) printf("%d ",pr[i]);ln;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
shai();
f[0][0]=1;
int i,j;
for (i=1;i<=prcnt;i++)
for (j=0;j<=n;j++)
{
f[i][j]=f[i-1][j];
for (LL tmp=pr[i];j>=tmp;tmp=tmp*pr[i])
f[i][j]+=f[i-1][j-tmp];
//printf("f[%d][%d]=%lld\n",i,j,f[i][j]);
}
LL ans=0;
for (i=0;i<=n;i++) ans+=f[prcnt][i];
printf("%lld\n",ans);
return 0;
}Problem1026
#include<cstdio>
using namespace std;
#define LL long long
LL f[20][11],A,B;
LL abs(LL x) {return x>0?x:-x;}
void prepare()
{
//f[i][j]:i位数，最高位是j的windy数的个数
//f[i][j]=sigma(f[i-1][k])
int i,j,k;
for (i=0;i<=9;i++) f[1][i]=1;
for (i=2;i<=10;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
if (abs(j-k)>=2) f[i][j]+=f[i-1][k];
//for (i=1;i<=10;i++) for (j=0;j<=9;j++) printf("%d %d: %lld\n",i,j,f[i][j]);
}
LL calc(int n)
{
n++;
int i,j;
int a[20];
a[0]=0;
int tmp=n;
while (tmp>0)
{
a[++a[0]]=tmp%10;
tmp/=10;
}
//printf("%d\n",a[0]);
LL ans=0;
for (i=1;i<a[0];i++)
for (j=1;j<=9;j++) ans+=f[i][j];
for (i=1;i<a[a[0]];i++) ans+=f[a[0]][i];
for (i=a[0]-1;i>0;i--)
{
for (j=0;j<=a[i]-1;j++)
if (abs(j-a[i+1])>=2) ans+=f[i][j];
if (abs(a[i]-a[i+1])<2) break;
}
return ans;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%lld%lld",&A,&B);
prepare();
printf("%lld\n",calc(B)-calc(A-1));
return 0;
}
Problem1029
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int NN=151111;
int n;
struct building
{
int x,y;
friend bool operator <(building a,building b) {return a.x<b.x;}
} a[NN];
priority_queue<building> Q;
bool cmp(building a,building b) {return a.y<b.y;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
int now=0,ans=0;
for (i=1;i<=n;i++)
{
if (now+a[i].x<=a[i].y)
{
ans++;
now+=a[i].x;
Q.push(a[i]);
}
else
{
building tmp=Q.top();
if (tmp.x>=a[i].x)
{
Q.pop();
Q.push(a[i]);
now=now-tmp.x+a[i].x;
}
}
}
printf("%d\n",ans);
return 0;
}Problem1030
#include<cstdio>
#include<cstring>
using namespace std;
#define mo 10007
const int AA=6011,NN=105;
int son[AA][26],fail[AA],q[AA],f[NN][AA];
int n,m,TTT;
bool flag[AA];
char s[63];
void ACins(int l)
{
int now=1;
for (int i=1;i<=l;i++)
{
int t=s[i]-'A';
if (son[now][t]) now=son[now][t];
else now=son[now][t]=++TTT;
}
flag[now]=true;
}
void buildfail()
{
int head=0,tail=1;
q[1]=1;
while (head<tail)
{
int x=q[++head];
flag[x]|=flag[fail[x]];
for (int i=0;i<26;i++)
if (son[x][i]==0) son[x][i]=son[fail[x]][i];
else
{
fail[son[x][i]]=son[fail[x]][i];
q[++tail]=son[x][i];
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d\n",&n,&m);
int i,j,k;
for (i=0;i<26;i++) son[0][i]=1,son[1][i]=0;
TTT=1;
for (i=1;i<=n;i++)
{
scanf("%s\n",s+1);
ACins(strlen(s+1));
}
buildfail();
int ans=1;
int li=200000;
for (i=1;i<=m;i++)
{
ans*=26;
if (ans>=li) ans%=mo;
}
f[0][1]=1;
for (i=0;i<m;i++)
for (j=1;j<=TTT;j++) if (!flag[j])
for (k=0;k<26;k++)
{
int t=son[j][k];
if (flag[t]) continue;
f[i+1][t]+=f[i][j];
if (f[i+1][t]>mo) f[i+1][t]-=mo;
}
for (i=1;i<=TTT;i++)
{
ans-=f[m][i];
if (ans<0) ans+=mo;
}
printf("%d\n",ans);
return 0;
}Problem1031
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rank[2100000],sa[2100000],sum[2100000],s[2100000],sa2[2100000],wv[2100000],height[2100000];
char sss[2100000];
int n,len;
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
memset(x,-1,sizeof(x)*(n+100000));
memset(y,-1,sizeof(y)*(n+100000));
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (j=p=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
//printf("sa: ");for (i=0;i<n;i++) printf("%d ",sa[i]);printf("\n");
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
gets(sss);
len=strlen(sss);
int i;
for (i=0;i<len;i++) s[i]=sss[i];
n=len*2-1;
for (i=len;i<n;i++) s[i]=s[i-len];
//for (i=0;i<n;i++) printf("%c",s[i]);printf("\n");
suffix_array(s,n,300);
for (i=0;i<n;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rank[4100000],sa[4100000],sum[4100000],s[4100000],sa2[4100000],wv[4100000],height[4100000];
char sss[4100000];
int n,len;
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
memset(x,-1,sizeof(x)*(n+100000));
memset(y,-1,sizeof(y)*(n+100000));
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (j=p=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
p=0;
for (i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
if (i==j) continue;
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
//printf("sa: ");for (i=0;i<n;i++) printf("%d ",sa[i]);printf("\n");
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
gets(sss);
len=strlen(sss);
int i;
for (i=0;i<len;i++) s[i]=sss[i];
n=len*2-1;
for (i=len;i<n;i++) s[i]=s[i-len];
//for (i=0;i<n;i++) printf("%c",s[i]);printf("\n");
suffix_array(s,n,300);
for (i=0;i<n;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rank[4100000],sa[4100000],sum[4100000],s[4100000],sa2[4100000],wv[4100000],height[4100000];
char sss[4100000];
int n,len;
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1)
{
sa[0]=0;
x[0]=0;
return;
}
memset(x,-1,sizeof(x)*400000);
memset(y,-1,sizeof(y)*400000);
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (j=p=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
p=0;
for (i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
gets(sss);
len=strlen(sss);
int i;
for (i=0;i<len;i++) s[i]=sss[i];
n=len*2-1;
for (i=len;i<n;i++) s[i]=s[i-len];
suffix_array(s,n,300);
for (i=0;i<n;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rank[4100000],sa[4100000],sum[4100000],s[4100000],sa2[4100000],wv[4100000],height[4100000];
char sss[4100000];
int n,len;
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1)
{
sa[0]=0;
x[0]=0;
return;
}
memset(x,-1,sizeof(x)*400000);
memset(y,-1,sizeof(y)*400000);
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (j=p=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
p=0;
for (i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",sss);
len=strlen(sss);
int i;
for (i=0;i<len;i++) s[i]=sss[i];
n=len*2-1;
for (i=len;i<n;i++) s[i]=s[i-len];
suffix_array(s,n,300);
for (i=0;i<n;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rank[410000],sa[410000],sum[410000],s[410000],sa2[410000],wv[410000],height[410000];
char sss[410000];
int n,len;
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1)
{
sa[0]=0;
x[0]=0;
return;
}
memset(x,-1,sizeof(x)*400000);
memset(y,-1,sizeof(y)*400000);
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (j=p=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
p=0;
for (i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",sss);
len=strlen(sss);
int i;
for (i=0;i<len;i++) s[i]=sss[i];
n=len*2-1;
for (i=len;i<n;i++) s[i]=s[i-len];
suffix_array(s,n,300);
for (i=0;i<n;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 4111101
int sa[NN],rank[NN],sa2[NN],sum[NN],wv[NN],height[NN],s[NN];
int len,i;
char ss[NN];
void suffix_array(int *r,int n,int m)
{
memset(rank,-1,sizeof(rank));
memset(sa2,-1,sizeof(sa2));
int i,j,p,*x=rank,*y=sa2,*t;
//for (i=0;i<n;i++) printf("%d ",x[i]);
if (n==1)
{
sa[0]=0,x[0]=0;
rank[0]=0;
return;
}
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (p=j=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
//for (i=0;i<n;i++) printf("%d ",x[i]);
for (p=0,i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",ss);
len=strlen(ss);
for (i=0;i<len;i++) s[i]=(int)ss[i];
for (i=len;i<len*2-1;i++) s[i]=s[i-len];
suffix_array(s,len*2-1,260);
for (i=0;i<len*2-1;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 4111101
int sa[NN],rank[NN],sa2[NN],sum[NN],wv[NN],height[NN],s[NN];
int len,i;
char ss[NN];
void suffix_array(int *r,int n,int m)
{
memset(rank,-1,sizeof(rank));
memset(sa2,-1,sizeof(sa2));
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1) {sa[0]=0,rank[0]=0;return;}
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (p=j=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
for (p=0,i=0;i<n;i++)
if (x[i]!=0)
{
j=sa[x[i]-1];
while (r[i+p]==r[j+p]) p++;
height[x[i]]=p;
if (p) p--;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",ss);
len=strlen(ss);
for (i=0;i<len;i++) s[i]=(int)ss[i];
for (i=len;i<len*2-1;i++) s[i]=s[i-len];
suffix_array(s,len*2-1,260);
for (i=0;i<len*2-1;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 4111101
int sa[NN],rank[NN],sa2[NN],sum[NN],wv[NN],height[NN],s[NN];
int len,i;
char ss[NN];
void suffix_array(int *r,int n,int m)
{
memset(rank,-1,sizeof(rank));
memset(sa2,-1,sizeof(sa2));
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1) {sa[0]=0,rank[0]=0;return;}
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[x[i]=r[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for (p=j=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) sum[i]=0;
for (i=0;i<n;i++) sum[wv[i]]++;
for (i=1;i<m;i++) sum[i]+=sum[i-1];
for (i=n-1;i>=0;i--) sa[--sum[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
}
}
int main()
{
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",ss);
len=strlen(ss);
for (i=0;i<len;i++) s[i]=(int)ss[i];
for (i=len;i<len*2-1;i++) s[i]=s[i-len];
suffix_array(s,len*2-1,260);
for (i=0;i<len*2-1;i++)
if (sa[i]<len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 4111101
int sa[NN],rank[NN],sa2[NN],sum[NN],wv[NN],height[NN],s[NN];
int len,i;
char ss[NN];
void suffix_array(int *r,int n,int m)
{
memset(rank,-1,sizeof(rank));
memset(sa2,-1,sizeof(sa2));
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1) {sa[1]=1,rank[1]=1;return;}
for (i=1;i<=m;i++) sum[i]=0;
for (i=1;i<=n;i++) sum[x[i]=r[i]]++;
for (i=2;i<=m;i++) sum[i]+=sum[i-1];
for (i=n;i;i--) sa[sum[x[i]]--]=i;
for (p=j=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j+1;i<=n;i++) y[++p]=i;
for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
for (i=1;i<=n;i++) wv[i]=x[y[i]];
for (i=1;i<=m;i++) sum[i]=0;
for (i=1;i<=n;i++) sum[wv[i]]++;
for (i=2;i<=m;i++) sum[i]+=sum[i-1];
for (i=n;i;i--) sa[sum[wv[i]]--]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[1]]=1,i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",ss+1);
len=strlen(ss+1);
for (i=1;i<=len;i++) s[i]=(int)ss[i];
for (i=len+1;i<=len*2-1;i++) s[i]=s[i-len];
suffix_array(s,len*2-1,260);
for (i=1;i<=len*2-1;i++)
if (sa[i]<=len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1031
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 4111101
int sa[NN],rank[NN],sa2[NN],sum[NN],wv[NN],height[NN],s[NN];
int len,i;
char ss[NN];
void suffix_array(int *r,int n,int m)
{
int i,j,p,*x=rank,*y=sa2,*t;
if (n==1) {sa[1]=1,rank[1]=1;return;}
for (i=0;i<=m;i++) sum[i]=0;
for (i=1;i<=n;i++) sum[x[i]=r[i]]++;
for (i=1;i<=m;i++) sum[i]+=sum[i-1];
for (i=n;i;i--) sa[sum[x[i]]--]=i;
for (p=j=1;p<n;j<<=1,m=p)
{
for (p=0,i=n-j+1;i<=n;i++) y[++p]=i;
for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
for (i=1;i<=n;i++) wv[i]=x[y[i]];
for (i=0;i<=m;i++) sum[i]=0;
for (i=1;i<=n;i++) sum[wv[i]]++;
for (i=1;i<=m;i++) sum[i]+=sum[i-1];
for (i=n;i;i--) sa[sum[wv[i]]--]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[1]]=1,i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",ss+1);
len=strlen(ss+1);
for (i=1;i<=len;i++) s[i]=(int)ss[i];
for (i=len+1;i<=len*2-1;i++) s[i]=s[i-len];
suffix_array(s,len*2-1,260);
for (i=1;i<=len*2-1;i++)
if (sa[i]<=len) printf("%c",s[sa[i]+len-1]);
printf("\n");
return 0;
}
Problem1032
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 500 + 5, INF = 999999999;
int n, Ans;
int A[MaxN], F[MaxN][MaxN];
inline int gmin(int a, int b) {return a < b ? a : b;}
int Solve(int l, int r)
{
if (F[l][r] != INF) return F[l][r];
if (l == r)
{
F[l][r] = 2;
return F[l][r];
}
int Temp = INF, Cntl, Cntr;
if (A[l] == A[r])
{
Cntl = Cntr = 0;
for (int i = l; i <= r; ++i)
{
if (A[i] == A[l]) ++Cntl;
else break;
}
for (int i = r; i >= l; --i)
{
if (A[i] == A[r]) ++Cntr;
else break;
}
if (Cntl + Cntr >= r - l + 1)
{
F[l][r] = 1;
return F[l][r];
}
if (Cntl + Cntr >= 3) Temp = gmin(Temp, Solve(l + Cntl, r - Cntr));
else Temp = gmin(Temp, Solve(l + Cntl, r - Cntr) + 1);
}
for (int i = l; i <= r - 1; ++i)
Temp = gmin(Temp, Solve(l, i) + Solve(i + 1, r));
F[l][r] = Temp;
return F[l][r];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
F[i][j] = INF;
Ans = Solve(1, n);
printf("%d\n", Ans);
return 0;
}Problem1034
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<deque>
#define inf 2000000000
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
int a[100005],b[100005];
int ans1,ans2;
set<int> q;
int solve(int a[],int b[])
{
int l1=1,r1=n,l2=1,r2=n,ans=0;
while(l1<=r1&&l2<=r2)
{
if(a[l1]>b[l2]){ans+=2;l1++;l2++;}
else if(a[r1]>b[r2]){ans+=2;r1--;r2--;}
else {ans+=(a[l1]==b[r2]);l1++;r2--;}
}
return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
sort(a+1,a+n+1);
sort(b+1,b+n+1);
printf("%d %d\n",solve(a,b),2*n-solve(b,a));
return 0;
}Problem1036
#include<cstdio>
#include<cmath>
using namespace std;
#define inf 99999999
#define NN 300055
int tsum[NN],tmax[NN],size[NN],deep[NN],root[NN],o[NN],w[NN],fa[NN],aa[NN*2][2];
int tot,n,m,anssum,ansmax;
char s[10];
int max(int a,int b) {return a>b?a:b;}
void swap(int &a,int &b) {int t=a;a=b;b=t;}
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
void buildtree(int v,int dep)
{
int rt=root[v];
deep[v]=dep;
size[rt]++;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
if (size[rt]<(int)sqrt(n)) root[y]=rt;
fa[y]=v;
buildtree(y,dep+1);
}
}
void dfs(int v,int ssum,int mmax)
{
ssum+=w[v];
mmax=max(mmax,w[v]);
tsum[v]=ssum;
tmax[v]=mmax;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
if (root[y]==root[v]) dfs(y,ssum,mmax);
}
}
void calc(int x,int y)
{
while (root[x]!=root[y])
{
if (deep[root[x]]<deep[root[y]]) swap(x,y);
anssum+=tsum[x];
ansmax=max(ansmax,tmax[x]);
x=fa[root[x]];
}
while (x!=y)
{
if (deep[x]<deep[y]) swap(x,y);
anssum+=w[x];
ansmax=max(ansmax,w[x]);
x=fa[x];
}
anssum+=w[x];
ansmax=max(ansmax,w[x]);
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;i++) scanf("%d",&w[i]),root[i]=i;
buildtree(1,1);
//printf("root: ");for (i=1;i<=n;i++) printf("%d ",root[i]);printf("\n");
for (i=1;i<=n;i++)
if (root[i]==i) dfs(i,0,-inf);
//printf("tmax: ");for (i=1;i<=n;i++) printf("%d ",tmax[i]);printf("\n");
//printf("tsum: ");for (i=1;i<=n;i++) printf("%d ",tsum[i]);printf("\n");
scanf("%d\n",&m);
for (;m;m--)
{
scanf("%s %d%d\n",s+1,&x,&y);
if (s[1]=='C')
{
w[x]=y;
if (root[x]==x) dfs(x,0,-inf);
else dfs(x,tsum[fa[x]],tmax[fa[x]]);
}
else
{
anssum=0,ansmax=-inf;
calc(x,y);
if (s[2]=='M') printf("%d\n",ansmax);
else printf("%d\n",anssum);
}
}
return 0;
}
Problem1036
#include<cstdio>
using namespace std;
#define NN 31000
#define inf 99999999
int size[NN],up[NN],heavy[NN],fa[NN],pos[NN],which[NN],deep[NN];
int o[NN],aa[NN*2][2],w[NN],lc[NN*4],rc[NN*4],tmax[NN*4],tsum[NN*4];
int n,m,TOT,tot,cnt,ww,ee,ansmax,anssum;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int max(int a,int b) {return a>b?a:b;}
void dfs1(int v)
{
int tmp=0,mm=-inf;
size[v]=1;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
deep[y]=deep[v]+1;
dfs1(y);
size[v]+=size[y];
if (size[y]>mm) mm=size[y],tmp=y;
}
heavy[v]=tmp;
}
void dfs2(int v)
{
pos[v]=++cnt;
which[cnt]=v;
if (!heavy[v]) return;
up[heavy[v]]=up[v];
dfs2(heavy[v]);
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]||y==heavy[v]) continue;
up[y]=y;
dfs2(y);
}
}
void update(int v)
{
tmax[v]=max(tmax[lc[v]],tmax[rc[v]]);
tsum[v]=tsum[lc[v]]+tsum[rc[v]];
}
void buildseg(int &v,int l,int r)
{
if (!v) v=++TOT;
//printf("buildseg: %d %d %d\n",v,l,r);
if (r-l==1)
{
tmax[v]=tsum[v]=w[which[l]];
return;
}
int mid=(l+r)>>1;
buildseg(lc[v],l,mid);
buildseg(rc[v],mid,r);
update(v);
}
void change(int v,int l,int r,int i,int x)
{
if (r-l==1)
{
tmax[v]=tsum[v]=x;
return;
}
int mid=(l+r)>>1;
if (i<mid) change(lc[v],l,mid,i,x);
else change(rc[v],mid,r,i,x);
update(v);
}
void find(int v,int l,int r)
{
if (ww<=l&&r<=ee)
{
if (tmax[v]>ansmax) ansmax=tmax[v];
anssum+=tsum[v];
return;
}
int mid=(l+r)>>1;
if (ww<mid) find(lc[v],l,mid);
if (ee>mid) find(rc[v],mid,r);
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;i++) scanf("%d",&w[i]);
dfs1(1);
up[1]=1;
dfs2(1);
//printf("up: ");for (i=1;i<=n;i++) printf("%d ",up[i]);printf("\n");
//printf("heavy: ");for (i=1;i<=n;i++) printf("%d ",heavy[i]);printf("\n");
//printf("pos: ");for (i=1;i<=n;i++) printf("%d ",pos[i]);printf("\n");
buildseg(i=0,1,n+1);
scanf("%d\n",&m);
for (i=1;i<=m;i++)
{
char s[10];
scanf("%s%d%d\n",s,&x,&y);
if (s[0]=='C')
{
change(1,1,n+1,pos[x],y);
w[x]=y;
}
else
{
ansmax=-inf;
anssum=0;
while (up[x]!=up[y])
{
if (deep[up[x]]<deep[up[y]]) {int t=x;x=y;y=t;}
ww=pos[up[x]],ee=pos[x]+1;
find(1,1,n+1);
x=fa[up[x]];
}
if (deep[x]<deep[y]) {int t=x;x=y;y=t;}
ww=pos[y],ee=pos[x]+1;
find(1,1,n+1);
printf("%d\n",s[1]=='M'?ansmax:anssum);
}
}
return 0;
}
Problem1036
#include<cstdio>
using namespace std;
#define NN 31000
#define inf 99999999
int size[NN],up[NN],heavy[NN],fa[NN],pos[NN],which[NN],deep[NN];
int o[NN],aa[NN*2][2],w[NN],lc[NN*4],rc[NN*4],tmax[NN*4],tsum[NN*4];
int n,m,TOT,tot,cnt,ww,ee,ansmax,anssum;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int max(int a,int b) {return a>b?a:b;}
void dfs1(int v)
{
int tmp=0,mm=-inf;
size[v]=1;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
deep[y]=deep[v]+1;
dfs1(y);
size[v]+=size[y];
if (size[y]>mm) mm=size[y],tmp=y;
}
heavy[v]=tmp;
}
void dfs2(int v)
{
pos[v]=++cnt;
which[cnt]=v;
if (!heavy[v]) return;
up[heavy[v]]=up[v];
dfs2(heavy[v]);
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]||y==heavy[v]) continue;
up[y]=y;
dfs2(y);
}
}
void update(int v)
{
tmax[v]=max(tmax[lc[v]],tmax[rc[v]]);
tsum[v]=tsum[lc[v]]+tsum[rc[v]];
}
void buildseg(int &v,int l,int r)
{
if (!v) v=++TOT;
if (r-l==1)
{
tmax[v]=tsum[v]=w[which[l]];
return;
}
int mid=(l+r)>>1;
buildseg(lc[v],l,mid);
buildseg(rc[v],mid,r);
update(v);
}
void change(int v,int l,int r,int i,int x)
{
if (r-l==1)
{
tmax[v]=tsum[v]=x;
return;
}
int mid=(l+r)>>1;
if (i<mid) change(lc[v],l,mid,i,x);
else change(rc[v],mid,r,i,x);
update(v);
}
void find(int v,int l,int r)
{
if (ww<=l&&r<=ee)
{
if (tmax[v]>ansmax) ansmax=tmax[v];
anssum+=tsum[v];
return;
}
int mid=(l+r)>>1;
if (ww<mid) find(lc[v],l,mid);
if (ee>mid) find(rc[v],mid,r);
}
int main()
{
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;i++) scanf("%d",&w[i]);
dfs1(1);
up[1]=1;
dfs2(1);
buildseg(i=0,1,n+1);
scanf("%d\n",&m);
for (i=1;i<=m;i++)
{
char s[10];
scanf("%s%d%d\n",s,&x,&y);
if (s[0]=='C')
{
change(1,1,n+1,pos[x],y);
w[x]=y;
}
else
{
ansmax=-inf;
anssum=0;
while (up[x]!=up[y])
{
if (deep[up[x]]<deep[up[y]]) {int t=x;x=y;y=t;}
ww=pos[up[x]],ee=pos[x]+1;
find(1,1,n+1);
x=fa[up[x]];
}
if (deep[x]<deep[y]) {int t=x;x=y;y=t;}
ww=pos[y],ee=pos[x]+1;
find(1,1,n+1);
printf("%d\n",s[1]=='M'?ansmax:anssum);
}
}
return 0;
}
Problem1036
#include<cstdio>
using namespace std;
#define NN 31000
#define inf 99999999
int aa[NN*2][2],o[NN],fa[NN],tmax[NN],tsum[NN],w[NN],son[NN][2];
int n,m,tot,ans;
bool root[NN];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int max(int a,int b) {return a>b?a:b;}
void dfs(int v)
{
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
dfs(y);
}
}
void update(int v)
{
int x=son[v][0],y=son[v][1];
tmax[v]=max(w[v],max(tmax[x],tmax[y]));
tsum[v]=w[v]+tsum[x]+tsum[y];
}
void rotate(int t,int p)
{
int y=fa[t];
if (root[y]) root[t]=true,root[y]=false;
else
if (y==son[fa[y]][0]) son[fa[y]][0]=t;
else son[fa[y]][1]=t;
fa[t]=fa[y];
son[y][p^1]=son[t][p];
if (son[t][p]>0) fa[son[t][p]]=y;
son[t][p]=y;
fa[y]=t;
update(y),update(t);
}
void splay(int t)
{
while (!root[t])
{
int y=fa[t];
if (root[y])
if (t==son[y][0]) rotate(t,1);
else rotate(t,0);
else
if (y==son[fa[y]][0])
if (t==son[y][0]) rotate(y,1),rotate(t,1);
else rotate(t,0),rotate(t,1);
else
if (t==son[y][1]) rotate(y,0),rotate(t,0);
else rotate(t,1),rotate(t,0);
}
}
int access(int x)
{
int y=0;
for (;x>0;y=x,x=fa[x])
{
splay(x);
root[son[x][1]]=true;
son[x][1]=y;
root[y]=false;
update(x);
}
return y;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;i++)
{
scanf("%d",&w[i]);
root[i]=true;
tmax[i]=tsum[i]=w[i];
}
tsum[0]=0,tmax[0]=-inf;
dfs(1);
for (scanf("%d\n",&m);m;m--)
{
char s[10];
scanf("%s%d%d\n",s,&x,&y);
if (s[0]=='C')
{
w[x]=y;
splay(x);
}
else if (s[1]=='M')
{
access(x);
int k=access(y);
ans=max(w[k],tmax[son[k][1]]);
if (x!=k)
{
splay(x);
ans=max(ans,tmax[x]);
}
printf("%d\n",ans);
}
else
{
access(x);
int k=access(y);
ans=w[k]+tsum[son[k][1]];
if (x!=k)
{
splay(x);
ans+=tsum[x];
}
printf("%d\n",ans);
}
}
return 0;
}
Problem1036
#include<cstdio>
using namespace std;
#define NN 31000
#define inf 99999999
int aa[NN*2][2],o[NN],fa[NN],tmax[NN],tsum[NN],w[NN],son[NN][2],stack[NN],cur[NN];
int n,m,tot,ans;
bool root[NN];
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int max(int a,int b) {return a>b?a:b;}
void dfs(int v)
{
/*for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
dfs(y);
}*/
int top=1;
stack[top]=v;
cur[top]=o[v];
while (top)
{
int x=stack[top];
int p=cur[top];
if (p==0) {top--;continue;}
cur[top]=aa[p][0];
int y=aa[p][1];
if (y!=fa[x])
{
fa[y]=x;
stack[++top]=y;
cur[top]=o[y];
}
}
}
void update(int v)
{
int x=son[v][0],y=son[v][1];
tmax[v]=max(w[v],max(tmax[x],tmax[y]));
tsum[v]=w[v]+tsum[x]+tsum[y];
}
void rotate(int t,int p)
{
int y=fa[t];
if (root[y]) root[t]=true,root[y]=false;
else
if (y==son[fa[y]][0]) son[fa[y]][0]=t;
else son[fa[y]][1]=t;
fa[t]=fa[y];
son[y][p^1]=son[t][p];
if (son[t][p]>0) fa[son[t][p]]=y;
son[t][p]=y;
fa[y]=t;
update(y),update(t);
}
void splay(int t)
{
while (!root[t])
{
int y=fa[t];
if (root[y])
if (t==son[y][0]) rotate(t,1);
else rotate(t,0);
else
if (y==son[fa[y]][0])
if (t==son[y][0]) rotate(y,1),rotate(t,1);
else rotate(t,0),rotate(t,1);
else
if (t==son[y][1]) rotate(y,0),rotate(t,0);
else rotate(t,1),rotate(t,0);
}
}
int access(int x)
{
int y=0;
for (;x>0;y=x,x=fa[x])
{
splay(x);
root[son[x][1]]=true;
son[x][1]=y;
root[y]=false;
update(x);
}
return y;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;i++)
{
scanf("%d",&w[i]);
root[i]=true;
tmax[i]=tsum[i]=w[i];
}
tsum[0]=0,tmax[0]=-inf;
dfs(1);
for (scanf("%d\n",&m);m;m--)
{
char s[10];
scanf("%s%d%d\n",s,&x,&y);
if (s[0]=='C') w[x]=y,splay(x);
else if (s[1]=='M')
{
access(x);
int k=access(y);
ans=max(w[k],tmax[son[k][1]]);
if (x!=k)
{
splay(x);
ans=max(ans,tmax[x]);
}
printf("%d\n",ans);
}
else
{
access(x);
int k=access(y);
ans=w[k]+tsum[son[k][1]];
if (x!=k)
{
splay(x);
ans+=tsum[x];
}
printf("%d\n",ans);
}
}
return 0;
}
Problem1036
#include<cstdio>
#include<cmath>
using namespace std;
#define NN 301111
#define inf 99999999
int fa[NN],up[NN],deep[NN],size[NN],o[NN],aa[NN*2][2],tsum[NN],tmax[NN],w[NN];
int n,m,tot,sqrtn;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
void dfs(int v)
{
size[up[v]]++;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
deep[y]=deep[v]+1;
up[y]=size[up[v]]<sqrtn?up[v]:y;
dfs(y);
}
}
void maintain(int v,int mm,int ss)
{
//printf("%d\n",v);for (int i=1;i<=50000000;i++);
tmax[v]=mm=w[v]>mm?w[v]:mm;
tsum[v]=ss=ss+w[v];
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]||up[y]!=up[v]) continue;
maintain(y,mm,ss);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,x,y;
scanf("%d",&n);
sqrtn=(int)sqrt(n);
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;scanf("%d",&w[i++]));
up[1]=1;
dfs(1);
for (i=1;i<=n;i++)
if (up[i]==i) maintain(i,-inf,0);
for (scanf("%d",&m);m;m--)
{
char s[10];
scanf("%s %d%d\n",s+1,&x,&y);
if (s[1]=='C')
{
w[x]=y;
maintain(up[x],-inf,0);
}
else
{
int ans1=-inf,ans2=0;
while (up[x]!=up[y])
{
if (deep[up[x]]<deep[up[y]]) {int t=x;x=y;y=t;}
if (tmax[x]>ans1) ans1=tmax[x];
ans2+=tsum[x];
x=fa[up[x]];
}
while (x!=y)
{
if (deep[x]<deep[y]) {int t=x;x=y;y=t;}
if (w[x]>ans1) ans1=w[x];
ans2+=w[x];
x=fa[x];
}
if (w[x]>ans1) ans1=w[x];
ans2+=w[x];
if (s[2]=='M') printf("%d\n",ans1);
else printf("%d\n",ans2);
}
}
return 0;
}
Problem1036
#include<cstdio>
#include<cmath>
using namespace std;
#define NN 301111
#define inf 99999999
int fa[NN],up[NN],deep[NN],size[NN],o[NN],aa[NN*2][2],tsum[NN],tmax[NN],w[NN];
int n,m,tot,sqrtn;
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
void dfs(int v)
{
size[up[v]]++;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
deep[y]=deep[v]+1;
up[y]=size[up[v]]<sqrtn?up[v]:y;
dfs(y);
}
}
void maintain(int v,int mm,int ss)
{
//printf("%d\n",v);for (int i=1;i<=50000000;i++);
tmax[v]=mm=w[v]>mm?w[v]:mm;
tsum[v]=ss=ss+w[v];
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (y==fa[v]||up[y]!=up[v]) continue;
maintain(y,mm,ss);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,x,y;
scanf("%d",&n);
sqrtn=(int)sqrt(n);
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=1;i<=n;scanf("%d",&w[i++]));
up[1]=1;
dfs(1);
for (i=1;i<=n;i++)
if (up[i]==i) maintain(i,-inf,0);
for (scanf("%d",&m);m;m--)
{
char s[10];
scanf("%s %d%d\n",s+1,&x,&y);
if (s[1]=='C')
{
w[x]=y;
if (up[x]==x) maintain(x,-inf,0);
else maintain(x,tmax[fa[x]],tsum[fa[x]]);
}
else
{
int ans1=-inf,ans2=0;
while (up[x]!=up[y])
{
if (deep[up[x]]<deep[up[y]]) {int t=x;x=y;y=t;}
if (tmax[x]>ans1) ans1=tmax[x];
ans2+=tsum[x];
x=fa[up[x]];
}
while (x!=y)
{
if (deep[x]<deep[y]) {int t=x;x=y;y=t;}
if (w[x]>ans1) ans1=w[x];
ans2+=w[x];
x=fa[x];
}
if (w[x]>ans1) ans1=w[x];
ans2+=w[x];
if (s[2]=='M') printf("%d\n",ans1);
else printf("%d\n",ans2);
}
}
return 0;
}
Problem1036
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
#define inf 999999999
const int NN=31111;
int fa[NN],son[NN][2],key[NN],o[NN],aa[NN*2][2],cur[NN],sta[NN],tmax[NN],tsum[NN];
int n,m,tot=1,top;
bool rrr[NN],tag[NN];
void out(int*a,int l,int r){for(int i=l;i<=r;i++)printf("%d ",a[i]);ln;}
void dfs(int v)
{
sta[top=1]=v;
cur[v]=o[v];
while (top)
{
v=sta[top];
int p=cur[v],y=aa[p][1];
if (!p) {top--;continue;}
cur[v]=aa[p][0];
if (y==fa[v]) continue;
fa[y]=v;
sta[++top]=y;
cur[y]=o[y];
}
}
void rev(int v)
{
tag[v]=!tag[v];
swap(son[v][0],son[v][1]);
}
void pushdown(int v)
{
if (!tag[v]) return;
rev(son[v][0]),rev(son[v][1]);
tag[v]=false;
}
void update(int v)
{
int x=son[v][0],y=son[v][1];
tmax[v]=max(key[v],max(tmax[x],tmax[y]));
tsum[v]=tsum[x]+tsum[y]+key[v];
}
void rotate(int t,int p)
{
int y=fa[t];
pushdown(y),pushdown(t);
if (rrr[y]) rrr[y]=false,rrr[t]=true;
else if (y==son[fa[y]][0]) son[fa[y]][0]=t;
else son[fa[y]][1]=t;
fa[t]=fa[y];
son[y][p^1]=son[t][p];
if (son[t][p]) fa[son[t][p]]=y;
son[t][p]=y;
fa[y]=t;
update(y),update(t);
}
void splay(int t)
{
while (!rrr[t])
{
int y=fa[t];
if (rrr[y])
if (t==son[y][0]) rotate(t,1);
else rotate(t,0);
else
if (y==son[fa[y]][0])
if (t==son[y][0]) rotate(y,1),rotate(t,1);
else rotate(t,0),rotate(t,1);
else
if (t==son[y][1]) rotate(y,0),rotate(t,0);
else rotate(t,1),rotate(t,0);
}
update(t);
}
void access(int x)
{
int y=0;
for (;x;y=x,x=fa[x])
{
splay(x);
pushdown(x);
rrr[son[x][1]]=true;
son[x][1]=y;
rrr[y]=false;
update(x);
}
}
void makeroot(int v)
{
access(v);
splay(v);
rev(v);
}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);
}
dfs(1);
//printf("fa ");out(fa,1,n);
for (i=1;i<=n;i++)
{
scanf("%d",&key[i]);
rrr[i]=true;
tmax[i]=tsum[i]=key[i];
}
tmax[0]=-inf,tsum[0]=0;
for (scanf("%d\n",&m);m;m--)
{
char s[10];
scanf("%s%d%d\n",s+1,&x,&y);
//printf("\n---------- %s --------------------------------------------------------------\n",s+1);
if (s[1]=='Q'&&s[2]=='M')
{
makeroot(x);
access(y),splay(y);
printf("%d\n",tmax[y]);
}
else if (s[1]=='Q'&&s[2]=='S')
{
makeroot(x);
access(y),splay(y);
printf("%d\n",tsum[y]);
}
else
{
key[x]=y;
splay(x);
}
}
return 0;
}Problem1038
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double DD;
#define ln printf("\n")
const DD eps=1e-7,dinf=1e10;;
const int NN=1111;
int n,m,now,num[2];
int dcmp(DD x)
{
if (fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct point
{
DD x,y;
point(DD a=0,DD b=0) {x=a;y=b;}
void out() {printf("%.3f %.3f ",x,y);}
friend point operator +(point a,point b) {return point(a.x+b.x,a.y+b.y);}
friend point operator -(point a,point b) {return point(a.x-b.x,a.y-b.y);}
friend point operator *(DD t,point a) {return point(a.x*t,a.y*t);}
friend DD operator %(point a,point b) {return a.x*b.y-b.x*a.y;}
} q[NN],b[2][NN],a[NN];
bool linesegxj(point P,point v,point A,point B)
{
return dcmp(v%(A-P))*dcmp(v%(B-P))==-1;
}
point linejd(point P,point v,point Q,point w)
{
point u=P-Q;
DD t=(w%u)/(v%w);
return P+t*v;
}
void ins(point P,point v)
{
b[now][num[now]+1]=b[now][1];
now^=1;
num[now]=0;
for (int i=1;i<=num[now^1];i++)
{
point A=b[now^1][i],B=b[now^1][i+1];
if (dcmp(v%(A-P)>=0)) b[now][++num[now]]=A;
if (linesegxj(P,v,A,B))
b[now][++num[now]]=linejd(P,v,A,B-A);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i++) scanf("%lf",&q[i].x);
for (i=1;i<=n;i++) scanf("%lf",&q[i].y);
now=0;num[now]=4;
b[0][1]=point(-dinf,dinf);
b[0][2]=point(-dinf,-dinf);
b[0][3]=point(dinf,-dinf);
b[0][4]=point(dinf,dinf);
for (i=1;i<n;i++)
ins(q[i],q[i+1]-q[i]);
m=num[now];
for (i=1;i<=m;i++) a[i]=b[now][i];
//for (i=1;i<=m;i++) a[i].out(),ln;
a[m+1]=a[1];
DD ans=dinf;
for (i=1;i<=m;i++)
for (j=1;j<n;j++)
if (dcmp(a[i].x-q[j].x)*dcmp(a[i].x-q[j+1].x)<=0)
{
point P=linejd(a[i],point(0,1),q[j],q[j+1]-q[j]);
ans=min(ans,fabs(P.y-a[i].y));
}
//ln;printf("ans=%.3f\n",ans);ln;
for (j=1;j<=n;j++)
for (i=1;i<=m;i++)
if (dcmp(q[j].x-a[i].x)*dcmp(q[j].x-a[i+1].x)<=0)
{
point P=linejd(q[j],point(0,1),a[i],a[i+1]-a[i]);
ans=min(ans,fabs(P.y-q[j].y));
//printf("i=%d j=%d P:",i,j);P.out();printf("\nans=%.3f\n",ans);
}
printf("%.3f\n",ans);
return 0;
}Problem1040
#include<cstdio>
#include<cstring>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
#define maa(a,b) ((a)>(b)?(a):(b))
#define NN 1001111
#define LL long long
#define INF 9999999999999999ll
#define ln printf("\n")
int o[NN],aa[NN*2][2],low[NN],dfn[NN],from[NN],a[NN],b[NN],fa[NN];
int n,TIME,tot=1;
bool vt[NN];
LL f[NN],g[NN];
void out(int *a,int l,int r){for(int i=l;i<=r;i++)printf("%d ",a[i]);ln;}
void out(LL *a,int l,int r){for(int i=l;i<=r;i++)printf("%lld ",a[i]);ln;}
void dfs(int v)
{
int p,y;
low[v]=dfn[v]=++TIME;
vt[v]=true;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
//printf("%d %d\n",v,y);
if (vt[y]) low[v]=mii(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=mii(low[v],low[y]);
}
}
//printf("\n--------------------- dfsing %d -------------------\n",v);
f[v]=a[v],g[v]=0;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
//printf("0\n");
f[v]+=g[y];
g[v]+=maa(g[y],f[y]);
}
else if (p!=from[y]&&dfn[y]>dfn[v])
{
int i,x;
LL t1,t2,t3,t4;
b[0]=0;
for (x=y;x!=v;x=fa[x]) b[++b[0]]=x;
//printf("b ");out(b,1,b[0]);printf("f ");out(f,1,n);printf("g ");out(g,1,n);ln;
t1=0,t2=0;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
//printf("t3=%lld t4=%lld\n",t3,t4);
t1=t3,t2=t4;
}
g[v]+=maa(t1,t2);
//printf("g[%d]=%lld\n",v,g[v]);
t1=0,t2=-INF;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
t1=t3,t2=t4;
}
f[v]+=t2;
//printf("f[%d]=%lld\n",v,f[v]);
}
}
}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x;
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&x);
addedge(i,x),addedge(x,i);
}
LL ans=0;
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i),ans+=maa(f[i],g[i]);
//ln;printf("fa "),out(fa,1,n);printf("dfn "),out(dfn,1,n);printf("low "),out(low,1,n);ln;
//printf("f ");out(f,1,n);printf("g ");out(g,1,n);ln,ln;
printf("%lld\n",ans);
return 0;
}
Problem1040
#include<cstdio>
#include<cstring>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
#define maa(a,b) ((a)>(b)?(a):(b))
#define NN 1001111
#define LL long long
#define INF 9999999999999999ll
#define ln printf("\n")
int o[NN],aa[NN*2][2],low[NN],dfn[NN],from[NN],a[NN],b[NN],fa[NN];
int n,TIME,tot=1;
bool vt[NN];
LL f[NN],g[NN];
void dfs(int v)
{
int p,y;
low[v]=dfn[v]=++TIME;
vt[v]=true;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (vt[y]) low[v]=mii(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=mii(low[v],low[y]);
}
}
f[v]=a[v],g[v]=0;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
f[v]+=g[y];
g[v]+=maa(g[y],f[y]);
}
else if (p!=from[y]&&dfn[y]>dfn[v])
{
int i,x;
LL t1,t2,t3,t4;
b[0]=0;
for (x=y;x!=v;x=fa[x]) b[++b[0]]=x;
t1=0,t2=0;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
t1=t3,t2=t4;
}
g[v]+=maa(t1,t2);
t1=0,t2=-INF;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
t1=t3,t2=t4;
}
f[v]+=t2;
}
}
}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x;
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&x);
addedge(i,x),addedge(x,i);
}
LL ans=0;
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i),ans+=maa(f[i],g[i]);
printf("%lld\n",ans);
return 0;
}
Problem1040
#include<cstdio>
#include<cstring>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
#define maa(a,b) ((a)>(b)?(a):(b))
#define NN 1001111
#define LL long long
#define INF 9999999999999999ll
int o[NN],aa[NN*2][2],low[NN],dfn[NN],from[NN],a[NN],b[NN],fa[NN];
int n,TIME,tot=1;
bool vt[NN];
LL f[NN],g[NN];
void dfs(int v)
{
int p,y;
low[v]=dfn[v]=++TIME;
vt[v]=true;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (vt[y]) low[v]=mii(low[v],dfn[y]);
else
{
from[y]=p;
fa[y]=v;
dfs(y);
low[v]=mii(low[v],low[y]);
}
}
f[v]=a[v],g[v]=0;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (p==(from[v]^1)) continue;
if (p==from[y]&&low[y]>dfn[v])
{
f[v]+=g[y];
g[v]+=maa(g[y],f[y]);
}
else if (p!=from[y]&&dfn[y]>dfn[v])
{
int i,x;
LL t1,t2,t3,t4;
b[0]=0;
for (x=y;x!=v;x=fa[x]) b[++b[0]]=x;
t1=0,t2=0;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
t1=t3,t2=t4;
}
g[v]+=maa(t1,t2);
t1=0,t2=-INF;
for (i=1;i<=b[0];i++)
{
t3=t2+f[b[i]];
t4=maa(t1,t2)+g[b[i]];
t1=t3,t2=t4;
}
f[v]+=t2;
}
}
}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,x;
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&x);
addedge(i,x),addedge(x,i);
}
LL ans=0;
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i),ans+=maa(f[i],g[i]);
printf("%lld\n",ans);
return 0;
}
Problem1041
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
LL R;
LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}
LL check(LL n)
{
//printf("check %I64d\n",n);
LL res=0;
for (LL i=1;i*i<=n;i++)
{
LL x=i*i,y=n-x;
LL tmp=sqrt(y);
if (tmp*tmp!=y) continue;
if (x>=y) continue;
if (gcd(x,y)==1) res++;//,printf("%I64d %I64d\n",x,y);;
}
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%lld",&R);
R<<=1;
LL ans=0;
for (LL i=1;i*i<=R;i++) if (R%i==0)
{
ans+=check(R/i);
if (i*i!=R) ans+=check(i);
}
printf("%lld\n",ans*4+4);
return 0;
}Problem1042
#include<cstdio>
using namespace std;
#define LL long long
#define ln printf("\n")
int a[5],b[5],num,m;
LL f[101111],ans,now;
void dfs(int t)
{
if (t>4)
{
if (num&1) ans-=f[now];
else ans+=f[now];
return;
}
dfs(t+1);
if (now-(b[t]+1)*a[t]>=0)
{
now-=(b[t]+1)*a[t];
num++;
dfs(t+1);
num--;
now+=(b[t]+1)*a[t];
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,j,tes;
for (i=1;i<=4;i++) scanf("%d",&a[i]);
f[0]=1;
for (i=1;i<=4;i++)
for (j=0;j<=100000;j++)
if (j>=a[i]) f[j]+=f[j-a[i]];
//for (i=1;i<=10;i++)printf("%lld ",f[i]);ln;
for (scanf("%d",&tes);tes--;)
{
for (i=1;i<=4;i++) scanf("%d",&b[i]);
scanf("%d",&m);
ans=0;
now=m,num=0;
dfs(1);
printf("%lld\n",ans);
}
return 0;
}
Problem1042
#include<cstdio>
using namespace std;
#define LL long long
#define ln printf("\n")
int a[5],b[5],num,m;
LL f[101111],ans,now;
void dfs(int t)
{
if (t>4)
{
if (num==0) return;
if (num&1) ans-=f[now];
else ans+=f[now];
return;
}
dfs(t+1);
if (now-(b[t]+1)*a[t]>=0)
{
now-=(b[t]+1)*a[t];
num++;
dfs(t+1);
num--;
now+=(b[t]+1)*a[t];
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,j,tes;
for (i=1;i<=4;i++) scanf("%d",&a[i]);
f[0]=1;
for (i=1;i<=4;i++)
for (j=0;j<=100000;j++)
if (j>=a[i]) f[j]+=f[j-a[i]];
//for (i=1;i<=10;i++)printf("%lld ",f[i]);ln;
for (scanf("%d",&tes);tes--;)
{
for (i=1;i<=4;i++) scanf("%d",&b[i]);
scanf("%d",&m);
ans=f[m];
now=m,num=0;
dfs(1);
printf("%lld\n",ans);
}
return 0;
}
Problem1043
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define DD double
#define LD long double
#define NN 11000
const LD eps=1e-6;
const LD pai=3.141592653589793238;
LD r[NN];
int num,n;
struct point
{
LD x,y;
point (LD a=0,LD b=0) {x=a,y=b;}
friend point operator * (LD t,point a) {a.x*=t;a.y*=t;return a;}
friend point operator - (point a,point b) {a.x-=b.x;a.y-=b.y;return a;}
} a[NN];
LD dot(point a,point b) {return a.x*b.x+a.y*b.y;}
LD lenth(point a) {return sqrt(a.x*a.x+a.y*a.y);}
LD yuxiandingli(LD a,LD b,LD c)
{
LD tmp=(a*a+b*b-c*c)/(2*a*b);
return acos(tmp);
}
struct seg
{
LD pos;
bool flag;
friend bool operator < (seg a,seg b) {return a.pos<b.pos;}
} b[NN*2];
void push(LD x,LD y)
{
num++,b[num].pos=x,b[num].flag=true;
num++,b[num].pos=y,b[num].flag=false;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i++)
{
DD qwe,asd,zxc;
scanf("%lf%lf%lf",&qwe,&asd,&zxc);
r[i]=qwe,a[i].x=asd,a[i].y=zxc;
}
LD ans=0;
for (i=1;i<=n;i++)
{
//printf("\n----------------------------------------------\n");
//printf("%.3f\n",(DD)ans);
//printf("%d\n",i);
LD all,cnt,now,last;
num=0;
bool cover=false;
for (j=i+1;j<=n;j++)
{
LD dd=lenth(a[i]-a[j]);
if (r[j]-r[i]-dd>-eps) {cover=true;break;}
if (dd-r[i]-r[j]>-eps) continue;
if (r[i]-r[j]-dd>-eps) continue;
point v=a[j]-a[i];
LD sita=atan2(v.y,v.x);
LD alfa=yuxiandingli(dd,r[i],r[j]);
LD t1=sita-alfa,t2=sita+alfa;
//printf("%.3f %.3f\n",(DD)t1,(DD)t2);
if (t1-t2>eps) push(t1,pai),push(-pai,t2);
else if (t2-pai>eps) push(t1,pai),push(-pai,t2-pai*2);
else if (t1+pai<-eps) push(t1+pai*2,pai),push(-pai,t2);
else push(t1,t2);
}
//printf("%d\n",num);
if (cover) continue;
sort(b+1,b+num+1);
//printf("asdasdasd\n");
//for (int ii=1;ii<=num;ii++) printf("%.3f %d\n",(DD)b[ii].pos,b[ii].flag);
all=2*pai*r[i];
//printf("%d\n",i);
if (num==0) {ans+=all;continue;}
//printf("%.3f\n",(DD)all);
cnt=0;
now=0;
last=-pai;
for (j=1;j<=num;j++)
{
if (now) cnt+=b[j].pos-last;
if (b[j].flag) now++;else now--;
last=b[j].pos;
//printf("%d %.3f\n",j,(DD)cnt);
}
//printf("cnt=%.3f\n",(DD)cnt);
ans+=(2*pai-cnt)/2/pai*all;
//printf("%.3f\n",(DD)ans);
//printf("%d\n",i);
}
printf("%.3f\n",(DD)ans);
return 0;
}
Problem1045
var
a,s:array[0..1000000]of int64;
n,sum,ans,temp:int64;
i:longint;
procedure kp(l,r:longint);
var
i,j:longint;
x,y:int64;
begin
i:=l;j:=r;
x:=s[random(j-i+1)+i];
repeat
while s[i]<x do inc(i);
while s[j]>x do dec(j);
if i<=j then
begin
y:=s[i];
s[i]:=s[j];
s[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if i<r then kp(i,r);
if j>l then kp(l,j);
end;
begin
// assign(input,'sss.in');reset(input);
// assign(output,'sss.out');rewrite(output);
readln(n);
for i:=1 to n do
begin
readln(a[i]);
inc(sum,a[i]);
end;
sum:=sum div n;
for i:=1 to n do a[i]:=a[i]-sum;
s[0]:=0;
for i:=1 to n do s[i]:=s[i-1]+a[i];
kp(1,n);
temp:=-s[(n+1)div 2];
ans:=0;
for i:=1 to n do ans:=ans+abs(temp+s[i]);
writeln(ans);
//close(input);close(output);
end.Problem1046
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
const int NN=10111;
int a[NN],b[NN],c[NN],f[NN],ans[NN];
int n,m,K;
int cha(int x)
{
int l=1,r=n;
while (l<=r)
{
int mid=(l+r)>>1;
if (c[mid]==x) return mid;
if (x<c[mid]) r=mid-1;
else l=mid+1;
}
return -1;
}
inline int getmax(int i)
{
int res=0;
for (;i;i-=i&-i)
if (c[i]>res) res=c[i];
return res;
}
inline void change(int i,int x)
{
for (;i<=n;i+=i&-i)
if (x>c[i]) c[i]=x;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[n-i+1]=-a[i];
c[i]=-a[i];
}
sort(c+1,c+n+1);
for (i=1;i<=n;i++) b[i]=cha(b[i]);
//printf("b ");for (i=1;i<=n;i++) printf("%d ",b[i]);ln;printf("c ");for (i=1;i<=n;i++) printf("%d ",c[i]);ln;
for (i=1;i<=n;i++) c[i]=0;
for (i=1;i<=n;i++)
{
f[n-i+1]=getmax(b[i]-1)+1;
change(b[i],f[n-i+1]);
}
//printf("f ");for (i=1;i<=n;i++) printf("%d ",f[i]);ln;
for (scanf("%d",&m);m;m--)
{
scanf("%d",&K);
int cnt=0,last=0;
for (i=1;i<=n;i++)
if (f[i]>=K-cnt&&a[i]>last)
ans[++cnt]=a[i],last=a[i];
if (cnt<K) printf("Impossible");
else for (i=1;i<=K;i++)
printf(i==K?"%d":"%d ",ans[i]);
printf("\n");
}
return 0;
}Problem1047
#include<cstdio>
using namespace std;
#define mii(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
#define ln printf("\n")
const int NN=1011;
int a[NN][NN],ans[NN][NN][2],up[NN][NN],q[NN][2];
int n,m,K;
void work(int t)
{
int i,j,head,tail;
for (j=1;j<=m;j++)
{
//printf("\n--------------------- j=%d ---------------------------------------\n",j);
head=0,tail=0;
for (i=1;i<K;i++)
{
while (head<tail&&a[i][j]<=q[tail][0]) tail--;
tail++,q[tail][0]=a[i][j],q[tail][1]=i;
}
//printf("%d %d\n",head,tail);
for (i=K;i<=n;i++)
{
while (head<tail&&a[i][j]<=q[tail][0]) tail--;
tail++,q[tail][0]=a[i][j],q[tail][1]=i;
while (head<tail&&q[head+1][1]<i-K+1) head++;
up[i][j]=q[head+1][0];
}
}
for (i=K;i<=n;i++)
{
head=0,tail=0;
for (j=1;j<K;j++)
{
while (head<tail&&up[i][j]<=q[tail][0]) tail--;
tail++,q[tail][0]=up[i][j],q[tail][1]=j;
}
for (j=K;j<=m;j++)
{
while (head<tail&&up[i][j]<=q[tail][0]) tail--;
tail++,q[tail][0]=up[i][j],q[tail][1]=j;
while (head<tail&&q[head+1][1]<j-K+1) head++;
ans[i][j][t]=q[head+1][0];
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&m,&K);
if (K>mii(n,m)) K=mii(n,m);
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
work(0);
//ln;printf("up:\n");for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",up[i][j]);ln;}ln;
//ln;printf("ans[0]:\n");for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",ans[i][j][0]);ln;}ln;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) a[i][j]=-a[i][j];
work(1);
int res=inf;
for (i=1;i<=n;i++) if (i>=K)
for (j=1;j<=m;j++) if (j>=K)
{
int t=-ans[i][j][1]-ans[i][j][0];
if (t<res) res=t;
}
printf("%d\n",res);
return 0;
}
Problem1050
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double DD;
#define inf 1000000005
#define ln printf("\n")
const DD dinf=1e30;
const int NN=511,MM=5111;
int o[NN],aa[MM*2][3],que[NN],dl[NN],dist[NN],pre[NN];
int n,m,tot,head,tail,TIME,S,T;
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
struct edge
{
int u,v,w;
void in() {scanf("%d%d%d",&u,&v,&w);}
void add()
{
addedge(u,v,w),addedge(v,u,w);
head=0,tail=2;
que[1]=u,que[2]=v;
TIME++;
}
friend bool operator <(const edge &a,const edge &b) {return a.w>b.w;}
} e[MM];
int spfa()
{
while (head!=tail)
{
head++;if (head==NN+1) head=1;
int x=que[head];
dl[x]=TIME-1;
if (dist[x]==-1) continue;
for (int p=o[x];p;p=aa[p][0])
{
int y=aa[p][1],tmp=max(dist[x],aa[p][2]);
//printf("%d %d\n",x,y);
if (y==1||y==pre[x]) continue;
if (dist[y]==-1)
{
pre[y]=x;
dist[y]=max(dist[x],aa[p][2]);
tail++;if (tail==NN+1) tail=1;
que[tail]=y;
}
else if (dist[y]>tmp)
{
pre[y]=x;
dist[y]=tmp;
if (dl[y]!=TIME)
{
dl[y]=TIME;
tail++;if (tail==NN+1) tail=1;
que[tail]=y;
}
}
}
}
//printf("dist ");for (int i=1;i<=n;i++) printf("%d ",dist[i]);ln;
return dist[T];
}
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++) e[i].in();
scanf("%d%d",&S,&T);
sort(e+1,e+m+1);
for (i=1;i<=n;i++) dist[i]=-1;
dist[S]=0;
DD ans=dinf;
int fz,fm;
for (i=1;i<=m;i++)
{
//printf("\n------------------------------------------------------------\n");
e[i].add();
int tmp=spfa();
//printf("tmp=%d\n",tmp);
if (tmp==inf||tmp==-1) continue;
if (1.0*tmp/e[i].w<ans)
ans=1.0*tmp/e[i].w,fz=tmp,fm=e[i].w;
}
if (ans>dinf*0.5) {printf("IMPOSSIBLE\n");return 0;}
int tmp=gcd(fz,fm);
fz/=tmp,fm/=tmp;
if (fm==1) printf("%d\n",fz);
else printf("%d/%d\n",fz,fm);
return 0;
}Problem1050
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double DD;
#define inf 1000000005
#define ln printf("\n")
const DD dinf=1e30;
const int NN=511,MM=5111;
int o[NN],aa[MM*2][3],que[NN],dl[NN],dist[NN];
int n,m,tot,head,tail,TIME,S,T;
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
struct edge
{
int u,v,w;
void in() {scanf("%d%d%d",&u,&v,&w);}
void add()
{
addedge(u,v,w),addedge(v,u,w);
head=0,tail=2;
que[1]=u,que[2]=v;
TIME++;
}
friend bool operator <(const edge &a,const edge &b) {return a.w>b.w;}
} e[MM];
int spfa()
{
while (head!=tail)
{
head++;if (head==NN+1) head=1;
int x=que[head];
dl[x]=TIME-1;
if (dist[x]==-1) continue;
for (int p=o[x];p;p=aa[p][0])
{
int y=aa[p][1],tmp=max(dist[x],aa[p][2]);
if (dist[y]>tmp)
{
dist[y]=tmp;
if (dl[y]!=TIME)
{
dl[y]=TIME;
tail++;if (tail==NN+1) tail=1;
que[tail]=y;
}
}
}
}
return dist[T];
}
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int main()
{
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++) e[i].in();
scanf("%d%d",&S,&T);
sort(e+1,e+m+1);
for (i=1;i<=n;i++) dist[i]=inf;
dist[S]=0;
DD ans=dinf;
int fz,fm;
for (i=1;i<=m;i++)
{
e[i].add();
int tmp=spfa();
if (tmp==inf) continue;
if (1.0*tmp/e[i].w<ans)
ans=1.0*tmp/e[i].w,fz=tmp,fm=e[i].w;
}
if (ans>dinf*0.5) {printf("IMPOSSIBLE\n");return 0;}
int tmp=gcd(fz,fm);
fz/=tmp,fm/=tmp;
if (fm==1) printf("%d\n",fz);
else printf("%d/%d\n",fz,fm);
return 0;
}Problem1051
#include<cstdio>
using namespace std;
#define mii(a,b) (a<b?a:b)
const int NN=10011,MM=50011;
int dfn[NN],low[NN],sta[NN],belong[NN],out[NN],o[NN],aa[MM*2][2],num[NN];
int n,m,tot=1,top,TIME,cnt;
bool vt[NN];
struct edge {int a,b;} e[MM];
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
sta[++top]=v;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y])
{
vt[y]=true;
dfs(y);
low[v]=mii(low[v],low[y]);
}
else if (!belong[y])
low[v]=mii(low[v],dfn[y]);
}
if (low[v]==dfn[v])
{
cnt++;
while (sta[top+1]!=v)
{
int k=sta[top--];
belong[k]=cnt;
num[cnt]++;
}
}
}
void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&e[i].a,&e[i].b);
addedge(e[i].a,e[i].b);
}
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i);
for (i=1;i<=m;i++)
if (belong[e[i].a]!=belong[e[i].b])
out[belong[e[i].a]]++;
//for (i=1;i<=n;i++) printf("%d ",belong[i]);printf("\n");
int t=0;
for (i=1;i<=cnt;i++)
if (out[i]==0) t++;
if (t>1) {printf("0\n");return 0;}
for (i=1;i<=cnt;i++)
if (out[i]==0) {printf("%d\n",num[i]);return 0;}
return 0;
}Problem1051
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
const int NN=11111,MM=51111;
int o[NN],aa[MM][2],low[NN],dfn[NN],sta[NN],num[NN],belong[NN],du[NN];
int n,m,tot,TIME,cnt,top;
bool vt[NN];
struct edge
{
int u,v;
} e[MM];
inline void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
sta[++top]=v;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y])
{
dfs(y);
if (low[y]<low[v]) low[v]=low[y];
}
else if (!belong[y])
low[v]=min(low[v],dfn[y]);
}
if (low[v]==dfn[v])
{
cnt++;
while (sta[top+1]!=v)
{
num[cnt]++;
belong[sta[top--]]=cnt;
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&e[i].u,&e[i].v);
addedge(e[i].u,e[i].v);
}
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i);
//printf("belong ");for(i=1;i<=n;i++) printf("%d ",belong[i]);ln;
for (i=1;i<=m;i++)
if (belong[e[i].u]!=belong[e[i].v])
du[belong[e[i].u]]++;
int t=0;
for (i=1;i<=cnt;i++)
if (du[i]==0) t++;
if (t>1) {printf("0\n");return 0;}
for (i=1;i<=cnt;i++)
if (du[i]==0) printf("%d\n",num[i]);
return 0;
}Problem1051
program popular;
const
inf=100000;
var
n,m,a,b,top,number,num,i,k,t:longint;
aa,bb,cc:array[1..inf,0..1] of longint;
dfn,o1,o2,o3:array[1..inf] of longint;
tot1,tot2,tot3:longint;
inz:array[1..inf] of boolean;
zhan,low,kind,outt:array[1..inf] of longint;
ans,count,tmp:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b);
exit(a);
end;
procedure addedge(x,y,num:longint);
begin
case num of
1:begin
inc(tot1); aa[tot1,1]:=y; aa[tot1,0]:=o1[x]; o1[x]:=tot1;
end;
2:begin
inc(tot2); bb[tot2,1]:=y; bb[tot2,0]:=o2[x]; o2[x]:=tot2;
end;
3:begin
inc(tot3); cc[tot3,1]:=y; cc[tot3,0]:=o3[x]; o3[x]:=tot3;
inc(outt[x]);
end;
end;
end;
procedure dfs(x:longint);
var
t,k:longint;
begin
inc(number);
dfn[x]:=number;
low[x]:=number;
k:=o1[x];
inc(top);
zhan[top]:=x;
inz[x]:=true;
while k<>0 do
begin
t:=aa[k,1];
if dfn[t]=0 then
begin
dfs(t);
low[x]:=min(low[x],low[t]);
end
else
begin
if inz[t] then low[x]:=min(low[x],low[t]);
end;
k:=aa[k,0];
end;
if dfn[x]=low[x] then
begin
inc(num);
while zhan[top]<>x do
begin
t:=zhan[top];
kind[t]:=num;
addedge(num,t,2);
inz[t]:=false;
dec(top);
end;
t:=zhan[top];
kind[t]:=num;
addedge(num,t,2);
inz[t]:=false;
dec(top);
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(a,b);
addedge(a,b,1);
end;
for i:=1 to n do
if dfn[i]=0 then
dfs(i);
for i:=1 to n do
begin
k:=o1[i];
while k<>0 do
begin
t:=aa[k,1];
if kind[i]<>kind[t] then
begin
addedge(kind[i],kind[t],3);
end;
k:=aa[k,0];
end;
end;
for i:=1 to num do
begin
if outt[i]=0 then
begin
inc(count);
k:=o2[i];
while k<>0 do
begin
inc(ans);
k:=bb[k,0];
end;
end;
end;
if count>1 then writeln(0)
else writeln(ans);
end.
Problem1051
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
const int NN=11111,MM=51111;
int o[NN],aa[MM][2],low[NN],dfn[NN],sta[NN],num[NN],belong[NN],du[NN];
int n,m,tot,TIME,cnt,top;
bool vt[NN];
struct edge
{
int u,v;
} e[MM];
inline void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
sta[++top]=v;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y])
{
dfs(y);
if (low[y]<low[v]) low[v]=low[y];
}
else if (!belong[y])
low[v]=min(low[v],dfn[y]);
}
if (low[v]==dfn[v])
{
cnt++;
while (sta[top+1]!=v)
{
num[cnt]++;
belong[sta[top--]]=cnt;
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&e[i].u,&e[i].v);
addedge(e[i].u,e[i].v);
}
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i);
//printf("belong ");for(i=1;i<=n;i++) printf("%d ",belong[i]);ln;
for (i=1;i<=m;i++)
if (belong[e[i].u]!=belong[e[i].v])
du[belong[e[i].u]]++;
int t=0;
for (i=1;i<=cnt;i++)
if (du[i]==0) t++;
if (t>1) {printf("0\n");return 0;}
for (i=1;i<=cnt;i++)
if (du[i]==0) printf("%d\n",num[i]);
return 0;
}
Problem1051
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
const int NN=11111,MM=51111;
int o[NN],aa[MM][2],low[NN],dfn[NN],sta[NN],num[NN],belong[NN],du[NN];
int n,m,tot,TIME,cnt,top;
bool vt[NN];
struct edge
{
int u,v;
} e[MM];
inline void addedge(int p,int q)
{
tot++;
aa[tot][1]=q;
aa[tot][0]=o[p];
o[p]=tot;
}
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
sta[++top]=v;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y])
{
dfs(y);
if (low[y]<low[v]) low[v]=low[y];
}
else
low[v]=min(low[v],dfn[y]);
}
if (low[v]==dfn[v])
{
cnt++;
while (sta[top+1]!=v)
{
num[cnt]++;
belong[sta[top--]]=cnt;
}
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&e[i].u,&e[i].v);
addedge(e[i].u,e[i].v);
}
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i);
//printf("belong ");for(i=1;i<=n;i++) printf("%d ",belong[i]);ln;
for (i=1;i<=m;i++)
if (belong[e[i].u]!=belong[e[i].v])
du[belong[e[i].u]]++;
int t=0;
for (i=1;i<=cnt;i++)
if (du[i]==0) t++;
if (t>1) {printf("0\n");return 0;}
for (i=1;i<=cnt;i++)
if (du[i]==0) printf("%d\n",num[i]);
return 0;
}
Problem1055
#include<cstdio>
#include<cstring>
using namespace std;
const char h[4]={'W','I','N','G'};
int n,a[4];
char s[205],go[4][17][2];
bool can[205][205][4],vt[205][205][4];
int f(char ch)
{
for (int i=0;i<4;i++)
if (h[i]==ch) return i;
return 123123123;
}
bool dp(int l,int r,int c)
{
if (l==r) return f(s[l])==c;
if (vt[l][r][c]) return can[l][r][c];
vt[l][r][c]=true;
bool &res=can[l][r][c];
for (int i=1;i<=a[c];i++)
for (int j=l;j<r;j++)
if (dp(l,j,f(go[c][i][0]))&&dp(j+1,r,f(go[c][i][1])))
{res=true;break;}
//printf("dp %d %d %d = %d\n",l,r,c,res);
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int i,j;
for (i=0;i<4;i++) scanf("%d",&a[i]);scanf("\n");
for (i=0;i<4;i++)
for (j=1;j<=a[i];j++) scanf("%s\n",go[i][j]);
scanf("%s",s+1);
n=strlen(s+1);
bool flag=false;
for (i=0;i<4;i++)
if (dp(1,n,i))
{
flag=true;
printf("%c",h[i]);
}
if (!flag) printf("The name is wrong!\n");
return 0;
}Problem1057
#include<cstdio>
using namespace std;
#define NN 2011
#define maa(a,b) ((a)>(b)?(a):(b))
#define mii(a,b) ((a)<(b)?(a):(b))
#define sqr(x) ((x)*(x))
int a[NN][NN],left[NN][NN],right[NN][NN],up[NN][NN];
int n,m,i,j,ans1,ans2,now;
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if ((i+j)%2==0) a[i][j]^=1;
//for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",a[i][j]);printf("\n");}
for (j=1;j<=m;j++) left[0][j]=1,right[0][j]=m;
ans1=ans2=0;
for (i=1;i<=n;i++)
{
now=0;
for (j=1;j<=m;j++)
{
if (a[i][j]==0)
{
up[i][j]=up[i-1][j]+1;
left[i][j]=maa(now+1,left[i-1][j]);
}
else
{
up[i][j]=0;
left[i][j]=1;
now=j;
}
}
now=m+1;
for (j=m;j;j--)
{
if (a[i][j]==0)
{
right[i][j]=mii(now-1,right[i-1][j]);
int c=right[i][j]-left[i][j]+1,k=up[i][j],b=mii(c,k);
ans1=maa(ans1,sqr(b));
ans2=maa(ans2,c*k);
}
else
{
right[i][j]=m;
now=j;
}
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) a[i][j]^=1;
for (i=1;i<=n;i++)
{
now=0;
for (j=1;j<=m;j++)
{
if (a[i][j]==0)
{
up[i][j]=up[i-1][j]+1;
left[i][j]=maa(now+1,left[i-1][j]);
}
else
{
up[i][j]=0;
left[i][j]=1;
now=j;
}
}
now=m+1;
for (j=m;j;j--)
{
if (a[i][j]==0)
{
right[i][j]=mii(now-1,right[i-1][j]);
int c=right[i][j]-left[i][j]+1,k=up[i][j],b=mii(c,k);
ans1=maa(ans1,sqr(b));
ans2=maa(ans2,c*k);
}
else
{
right[i][j]=m;
now=j;
}
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
Problem1057
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
const int NN=2011;
int a[NN][NN],left[NN][NN],right[NN][NN],up[NN][NN];
int n,m;
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j;
for (i=1;i<=n;i++) for (j=1;j<=m;j++)
{
char ch=getchar();
while (ch!='0'&&ch!='1') ch=getchar();
a[i][j]=(ch=='1');
if ((i+j+1)&1) a[i][j]^=1;
}
//printf("a:\n");for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",a[i][j]);ln;}ln;
for (i=1;i<=m;i++) right[0][i]=m+1;
int ans1=0,ans2=0;
for (i=1;i<=n;i++)
{
int now=0;
for (j=1;j<=m;j++)
if (a[i][j]==1)
{
up[i][j]=0;
left[i][j]=1,now=j;
}
else
{
up[i][j]=up[i-1][j]+1;
left[i][j]=max(now+1,left[i-1][j]);
}
now=m+1;
for (j=m;j;j--)
if (a[i][j]==1)
{
right[i][j]=m;
now=j;
}
else
{
right[i][j]=min(now-1,right[i-1][j]);
int a=right[i][j]-left[i][j]+1,b=up[i][j];
ans1=max(ans1,min(a,b)*min(a,b));
ans2=max(ans2,a*b);
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) a[i][j]^=1;
for (i=1;i<=n;i++)
{
int now=0;
for (j=1;j<=m;j++)
if (a[i][j]==1)
{
up[i][j]=0;
left[i][j]=1,now=j;
}
else
{
up[i][j]=up[i-1][j]+1;
left[i][j]=max(now+1,left[i-1][j]);
}
now=m+1;
for (j=m;j;j--)
if (a[i][j]==1)
{
right[i][j]=m;
now=j;
}
else
{
right[i][j]=min(now-1,right[i-1][j]);
int a=right[i][j]-left[i][j]+1,b=up[i][j];
ans1=max(ans1,min(a,b)*min(a,b));
ans2=max(ans2,a*b);
}
}
//printf("left:\n");for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",left[i][j]);ln;}ln;
printf("%d\n%d\n",ans1,ans2);
return 0;
}Problem1058
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
#include <set>
#define MAXN 500005
#define INF 1000000007
using namespace std;
int n, m;
set<int>s, ss;
map<int, int>mp;
vector<int>g[MAXN];
int a[MAXN], b[MAXN];
int main()
{
scanf("%d%d", &n, &m);
int mg = INF, ms = INF, pos, val;
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
ss.insert(a[i]);
b[i] = a[i];
if(i)
{
int k = abs(a[i] - a[i - 1]);
s.insert(k);
mp[k]++;
}
}
sort(b, b + n);
for(int i = 1; i < n; i++)
ms = min(ms, b[i] - b[i - 1]);
mg = *s.begin();
char op[33];
while(m--)
{
scanf("%s", op);
if(op[4] == 'R')
{
scanf("%d%d", &pos, &val);
pos--;
g[pos].push_back(val);
if(ms)
{set<int>::iterator it = ss.lower_bound(val);
if(it != ss.begin())
{
if(it == ss.end())
{
it--;
ms = min(ms, abs(val - *it));
}
else
{
int x = *it;
it--;
int y = *it;
ms = min(ms, abs(x - val));
ms = min(ms, abs(y - val));
}
}
else ms = min(ms, abs(val - *ss.begin()));
}
ss.insert(val);
int x, y = INF;
if(g[pos].size() == 1) x = a[pos];
else x = g[pos][g[pos].size() - 2];
if(pos + 1 < n)
{
y = a[pos + 1];
int k = abs(x - y);
mp[k]--;
if(mp[k] == 0) s.erase(k);
k = abs(x - val);
s.insert(k);
mp[k]++;
k = abs(y - val);
s.insert(k);
mp[k]++;
mg = *s.begin();
}
else
{
int k = abs(x - val);
s.insert(k);
mp[k]++;
mg = *s.begin();
}
}
else if(op[4] == 'G') printf("%d\n", mg);
else printf("%d\n", ms);
}
return 0;
}Problem1059
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 999999999
#define mii(a,b) ((a)<(b)?(a):(b))
const int NN=405,MM=40111;
int q[NN],o[NN],cur[NN],deep[NN],aa[MM*2][3];
int tes,n,tot,S,T;
bool bfs()
{
int head=0,tail=1;
q[1]=S;
memset(deep,0,sizeof(deep));
deep[S]=1;
while (head<tail)
{
int x=q[++head];
cur[x]=o[x];
for (int p=o[x];p;p=aa[p][0])
{
int y=aa[p][1];
if (!deep[y]&&aa[p][2])
deep[y]=deep[x]+1,q[++tail]=y;
}
}
return deep[T];
}
int dfs(int v,int f)
{
if (v==T) return f;
int res=0;
for (int &p=cur[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (deep[y]!=deep[v]+1||!aa[p][2]) continue;
int tmp=dfs(y,mii(f,aa[p][2]));
f-=tmp,aa[p][2]-=tmp;
aa[p^1][2]+=tmp,res+=tmp;
if (!f) break;
}
if (!res) deep[v]=inf;
return res;
}
void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
void add(int p,int q,int v)
{
//printf("add %d %d %d\n",p,q,v);
addedge(p,q,v);
addedge(q,p,0);
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
for (scanf("%d",&tes);tes;tes--)
{
scanf("%d",&n);
memset(o,0,sizeof(o));
tot=1;
int i,j,x;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
scanf("%d",&x);
if (x) add(i,j+n,inf);
}
S=2*n+1,T=S+1;
for (i=1;i<=n;i++) add(S,i,1),add(i+n,T,1);
int ans=0;
while (bfs()) ans+=dfs(S,inf);
if (ans==n) printf("Yes\n");
else printf("No\n");
}
return 0;
}Problem1061
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define eps 1e-7
#define INF 1e10
using namespace std;
int n,m;
namespace Lp{
double A[10100][1010],b[10100],c[1010],v;
void print()
{
return;
for(int i=1;i<=n;i++) printf("%lf ",c[i]);puts("");
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
printf("%lf ",A[i][j]);
}puts("");
}
for(int i=1;i<=m;i++) printf("%lf ",b[i]);puts("");
puts("");
}
void pivot(int l,int e){
int i,j;
b[l]/=A[l][e];
for(i=1;i<=n;i++)
if(i!=e)
A[l][i]/=A[l][e];
A[l][e]=1/A[l][e];
for(i=1;i<=m;i++){
if(i!=l&&fabs(A[i][e])>eps)
{
b[i]-=A[i][e]*b[l];
for(j=1;j<=n;j++)
if(j!=e)
A[i][j]-=A[i][e]*A[l][j];
A[i][e]=-A[i][e]*A[l][e];
}
}
v+=c[e]*b[l];
for(i=1;i<=n;i++)
if(i!=e)
c[i]-=c[e]*A[l][i];
c[e]=-c[e]*A[l][e];
print();
}
double Simplex(){
int i,l,e;
while(1)
{
for(i=1;i<=n;i++)
if(c[i]>eps) break;
if((e=i)==n+1) return v;
double temp=INF;
for(i=1;i<=m;i++)
if(A[i][e]>eps&&b[i]/A[i][e]<temp)
temp=b[i]/A[i][e],l=i;
if(temp==INF) return INF;
pivot(l,e);
}
}
}
int main()
{
using namespace Lp;
int i,j,x,y,z;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%lf",&c[i]);
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
for(j=x;j<=y;j++)
A[i][j]=1;
b[i]=z;
}
print();
double ans=Simplex();
printf("%d\n",(int)(ans+0.5));
return 0;
}
Problem1064
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NN=101111,MM=1001111;
int o[NN],aa[MM*2][3],f[NN];
int n,m,tot,maxx,minx,ans1,ans2;
bool vt[NN];
inline void addedge(int p,int q,int v)
{
tot++;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][0]=o[p];
o[p]=tot;
}
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
void dfs1(int v)
{
vt[v]=true;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (vt[y]) ans1=gcd(ans1,abs(f[v]+aa[p][2]-f[y]));
else f[y]=f[v]+aa[p][2],dfs1(y);
}
}
void dfs2(int v)
{
vt[v]=true;
maxx=max(maxx,f[v]);
minx=min(minx,f[v]);
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y]) f[y]=f[v]+aa[p][2],dfs2(y);
}
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y,1),addedge(y,x,-1);
}
ans1=0;
for (i=1;i<=n;i++)
if (!vt[i]) dfs1(i);
//printf("ans1=%d\n",ans1);
if (ans1>0)
{
ans2=3;
while (ans2<ans1&&ans1%ans2) ans2++;
}
else
{
memset(vt,0,sizeof(vt));
memset(f,0,sizeof(0));
for (i=1;i<=n;i++) if (!vt[i])
{
maxx=minx=0;
dfs2(i);
ans1+=maxx-minx+1;
}
ans2=3;
}
if (ans1<3) printf("-1 -1\n");
else printf("%d %d\n",ans1,ans2);
return 0;
}Problem1069
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ln printf("\n")
typedef double DD;
const DD eps=1e-7;
const int NN=4111;
int n,num;
struct point
{
DD x,y;
void in() {scanf("%lf%lf",&x,&y);}
void out() {printf("%.3f %.3f\n",x,y);}
friend bool operator <(point a,point b) {return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
friend point operator -(point a,point b) {a.x-=b.x;a.y-=b.y;return a;}
friend DD operator %(point a,point b) {return a.x*b.y-b.x*a.y;}
} a[NN],b[NN];
DD calc(point A,point B,point C,point D)
{
DD res=A%B+B%C+C%D+D%A;
return fabs(res)*0.5;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1;i<=n;i++) a[i].in();
sort(a+1,a+n+1);
//for (i=1;i<=n;i++) a[i].out();ln;
for (i=1;i<=n;i++)
{
while (num>1&&(b[num]-b[num-1])%(a[i]-b[num-1])<eps) num--;
b[++num]=a[i];
}
int t=num;
for (i=n-1;i;i--)
{
while (num>t&&(b[num]-b[num-1])%(a[i]-b[num-1])<eps) num--;
b[++num]=a[i];
}
num--;
for (i=1;i<=num;i++) b[i+num]=b[i];
//for (i=1;i<=num;i++) b[i].out();ln;
DD ans=0;
for (i=1;i<num;i++)
{
int n1=i,n2=i+1;
for (int j=i+1;j<=num;j++)
{
while ((b[j]-b[i])%(b[n2+1]-b[i])>(b[j]-b[i])%(b[n2]-b[i])) n2++;
while ((b[n1+1]-b[i])%(b[j]-b[i])>(b[n1]-b[i])%(b[j]-b[i])) n1++;
//printf("%d %d %d\n",j,n1,n2);printf("%.3f\n",(b[j]-b[i])%(b[n2+1]-b[i]));(b[j]-b[i]).out(),(b[n2+1]-b[i]).out();
ans=max(ans,calc(b[i],b[n1],b[j],b[n2]));
}
}
printf("%.3f\n",ans);
return 0;
}Problem1070
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=99999999;
int aa[1000000][4],o[100000],dist[100000],a[1000][1000],hao[1000][1000],pre[100000],q[1000000];
bool dl[100000];
int n,m,i,j,k,num,S,T,head,tail,tot,ans;
int min(int a,int b) {return a<b?a:b;}
void add(int p,int q,int v,int cost)
{
++tot;
aa[tot][1]=q;
aa[tot][2]=v;
aa[tot][3]=cost;
aa[tot][0]=o[p];
o[p]=tot;
}
void addedge(int p,int q,int v,int cost)
{
add(p,q,v,cost);
add(q,p,0,-cost);
}
void init()
{
scanf("%d%d",&m,&n);//m,n表示技术人员数与顾客数
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) scanf("%d",&a[i][j]);//第j位技术人员维修第i辆车
num=n;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) hao[i][j]=++num;
S=++num,T=++num;
tot=1;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) addedge(S,hao[i][j],1,0);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++) addedge(hao[i][j],k,1,(n-(j-1))*a[k][i]);
for (i=1;i<=n;i++) addedge(i,T,1,0);
}
bool relax(int x,int y,int v)
{
if (dist[y]>dist[x]+v)
{
dist[y]=dist[x]+v;
return 1;
}
return 0;
}
bool spfa()
{
memset(dist,127,sizeof(dist[0])*(T+10));
head=tail=0;
memset(dl,0,sizeof(dl[0])*(T+10));
dist[S]=0;
dl[S]=1;
q[++tail]=S;
while (head<tail)
{
int x=q[++head];
dl[x]=0;
int p=o[x];
while (p)
{
int y=aa[p][1];
if (aa[p][2]&&relax(x,y,aa[p][3]))
{
pre[y]=p;
if (!dl[y])
{
q[++tail]=y;
dl[y]=1;
}
}
p=aa[p][0];
}
}
if (dist[T]==dist[T+1]) return 0;
return 1;
}
void addcost()
{
int p=pre[T],flow=inf;
while (p)
{
flow=min(flow,aa[p][2]);
p=pre[aa[p^1][1]];
}
p=pre[T];
while (p)
{
ans+=flow*aa[p][3];
aa[p][2]-=flow;
aa[p^1][2]+=flow;
p=pre[aa[p^1][1]];
}
}
void doit()
{
ans=0;
while (spfa()) addcost();
printf("%.2f\n",ans*1.0/n);
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
init();
doit();
return 0;
}
Problem1072
#include<cstdio>
#include<cstring>
using namespace std;
int tc,n,mo,S,i,k,ans,f[1100][1<<10],flag[15];
char s[15];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&tc);
for (;tc;tc--)
{
scanf("%s",s+1);
n=strlen(s+1);
scanf("%d\n",&mo);
memset(f,0,sizeof(f));
f[0][0]=1;
for (S=0;S<1<<n;S++)
for (i=0;i<mo;i++)
for (k=1;k<=n;k++)
if (((1<<(k-1))&S)==0)
f[(i*10+s[k]-'0')%mo][S^(1<<(k-1))]+=f[i][S];
ans=f[0][(1<<n)-1];
for (i=1;i<=n;i++) flag[s[i]-'0']++;
for (i=0;i<10;i++)
while (flag[i]) ans/=flag[i],flag[i]--;
printf("%d\n",ans);
}
return 0;
}
Problem1076
#include<cstdio>
#include<cstring>
using namespace std;
#define DD double
#define inf 99999999
int P[120],mast[120],n,kk,i,S,j,x;
DD f[120][1<<15];
DD max(DD a,DD b) {return a>b?a:b;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&kk,&n);
for (i=1;i<=n;i++)
{
scanf("%d",&P[i]);
for (scanf("%d",&x);x;scanf("%d",&x)) mast[i]+=(1<<(x-1));
}
for (i=kk;i;i--)
for (S=0;S<1<<n;S++)
for (j=1;j<=n;j++)
if ((mast[j]&S)!=mast[j]) f[i][S]+=f[i+1][S]/n;
else f[i][S]+=max(f[i+1][S|(1<<(j-1))]+P[j],f[i+1][S])/n;
printf("%.6f\n",f[1][0]);
return 0;
}
Problem1078
#include<cstdio>
#include<algorithm>
using namespace std;
#define ln printf("\n")
int lc[111],rc[111],fa[111],ans[111];
int n,root;
void out(int *a,int l,int r) {for (int i=l;i<=r;i++)printf("%d ",a[i]);ln;}
int work()
{
//printf("\n----------------------- work ------------------------------\n");
int x=root;
for (;;)
{
if (!rc[x]) break;
x=lc[x];
}
if (lc[x]&&!lc[lc[x]]&&!rc[lc[x]]) x=lc[x];
int t=x,f=fa[x];
if (x==root) root=lc[root],fa[root]=-1;
//printf("x=%d t=%d f=%d\n",x,t,f);
if (lc[x]) fa[lc[x]]=f;
if (f!=-1) lc[f]=lc[x];
for (x=f;x!=-1;x=fa[x]) swap(lc[x],rc[x]);
return t;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
fa[0]=-1;
int i,x;
for (i=1;i<=n;i++)
{
scanf("%d",&x);
if (x<100) lc[x]=i,fa[i]=x;
else rc[x-100]=i,fa[i]=x-100;
}
//printf("fa ");out(fa,0,n);printf("lc ");out(lc,0,n);printf("rc ");out(rc,0,n);ln;
for (i=0;i<=n;i++) ans[i]=work();
for (i=n;i>=0;i--) printf("%d ",ans[i]);
return 0;
}Problem1079
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <ctime>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>
#define ll long long
#define p 1000000007
using namespace std;
ll f[16][16][16][16][16][16];
int k,c[20],x;
bool v[16][16][16][16][16][16];
ll dp(int a,int b,int c,int d,int e,int last)
{
if (v[a][b][c][d][e][last]) return f[a][b][c][d][e][last];
if (a+b+c+d+e==0) return 1;
ll sum=0;
if (a) sum+=(a-(last==2))*dp(a-1,b,c,d,e,1);
if (b) sum+=(b-(last==3))*dp(a+1,b-1,c,d,e,2);
if (c) sum+=(c-(last==4))*dp(a,b+1,c-1,d,e,3);
if (d) sum+=(d-(last==5))*dp(a,b,c+1,d-1,e,4);
if (e) sum+=e*dp(a,b,c,d+1,e-1,5);
v[a][b][c][d][e][last]=1;
return f[a][b][c][d][e][last]=(sum%p);
}
int main()
{
scanf("%d",&k);
while (k--) {scanf("%d",&x);c[x]++;}
cout<<dp(c[1],c[2],c[3],c[4],c[5],0);
}
Problem1083
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,fa[1000];
struct edge
{
int u,v,w;
void in() {scanf("%d%d%d",&u,&v,&w);}
friend bool operator <(edge a,edge b) {return a.w<b.w;}
} e[10000];
int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++) e[i].in();
sort(e+1,e+m+1);
for (i=1;i<=n;i++) fa[i]=i;
int cnt=0,ans=0;
for (i=1;i<=m&&cnt<n-1;i++)
{
int x=getfa(e[i].u),y=getfa(e[i].v);
if (x==y) continue;
cnt++;
fa[x]=y;
ans=e[i].w;
}
printf("%d %d\n",n-1,ans);
return 0;
}Problem1084
#include<cstdio>
using namespace std;
#define inf 999999999
int n,m,K,a[111][3];
inline void renew(int &x,int y) {if (y>x) x=y;}
int work1()
{
static int sum[111],f[111][13];
int i,j,k;
for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
for (i=1;i<=n;i++)
for (j=1;j<=i&&j<=K;j++)
{
f[i][j]=f[i-1][j];
for (k=0;k<i;k++)
renew(f[i][j],f[k][j-1]+sum[i]-sum[k]);
}
return f[n][K];
}
int work2()
{
static int s1[111],s2[111],f[111][111][13];
int i,j,k,l;
for (i=1;i<=n;i++)
s1[i]=s1[i-1]+a[i][1],s2[i]=s2[i-1]+a[i][2];
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
for (k=1;k<=K;k++)
{
if (i) renew(f[i][j][k],f[i-1][j][k]);
if (j) renew(f[i][j][k],f[i][j-1][k]);
if (i==j)
for (l=0;l<i&&l<j;l++)
renew(f[i][j][k],f[l][l][k-1]+s1[i]-s1[l]+s2[j]-s2[l]);
for (l=0;l<i;l++)
renew(f[i][j][k],f[l][j][k-1]+s1[i]-s1[l]);
for (l=0;l<j;l++)
renew(f[i][j][k],f[i][l][k-1]+s2[j]-s2[l]);
}
return f[n][n][K];
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&m,&K);
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
if (m==1) printf("%d\n",work1());
else printf("%d\n",work2());
return 0;
}Problem1085
const
a0:array[1..5,1..5]of longint=((1,1,1,1,1),
(0,1,1,1,1),
(0,0,-1,1,1),
(0,0,0,0,1),
(0,0,0,0,0));
dx:array[1..8]of longint=(-2,-2,-1,-1,1,1,2,2);
dy:array[1..8]of longint=(1,-1,2,-2,2,-2,1,-1);
var
a:array[1..5,1..5]of longint;
tt,i,j,ans,x0,y0:longint;
ch:char;
procedure init;
begin
for i:=1 to 5 do
begin
for j:=1 to 5 do
begin
read(ch);
if ch<>'*' then a[i,j]:=ord(ch)-ord('0')
else
begin
a[i,j]:=-1;
x0:=i;
y0:=j;
end;
end;
readln;
end;
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
function check:boolean;
var i,j:longint;
begin
for i:=1 to 5 do
for j:=1 to 5 do
if a[i,j]<>a0[i,j] then exit(false);
exit(true);
end;
function gu:longint;
var res,i,j:longint;
begin
res:=0;
for i:=1 to 5 do
for j:=1 to 5 do
if a[i,j]<>a0[i,j] then inc(res);
exit(res-1);
end;
function dfs(x,y,dep:longint):boolean;
var i,xx,yy:longint;
begin
if check then exit(true);
if dep>=ans then exit(false);
if dep+gu>ans then exit(false);
for i:=1 to 8 do
begin
xx:=x+dx[i];
yy:=y+dy[i];
if(xx<1)or(xx>5)or(yy<1)or(yy>5)then continue;
swap(a[x,y],a[xx,yy]);
if dfs(xx,yy,dep+1) then exit(true);
swap(a[x,y],a[xx,yy]);
end;
exit(false);
end;
procedure doit;
begin
for ans:=0 to 15 do
if dfs(x0,y0,0) then
begin
writeln(ans);
exit;
end;
writeln(-1);
end;
begin
// assign(input,'sss.in');reset(input);
//assign(output,'sss.out');rewrite(output);
readln(tt);
repeat
dec(tt);
init;
doit;
until tt=0;
// close(input);close(output);
end.Problem1086
#include<cstdio>
#include<vector>
using namespace std;
#define ln printf("\n")
#define NN 1111
int sta[NN][NN*2],top[NN],belong[NN],shenghui[NN],o[NN],aa[NN*2][2],fa[NN];
int n,B,cnt,tot;
void dfs(int v)
{
int p,y;
for (p=o[v];p;p=aa[p][0])
{
y=aa[p][1];
if (y==fa[v]) continue;
fa[y]=v;
dfs(y);
if (top[v]>=B)
{
cnt++;
for (;top[v];top[v]--) belong[sta[v][top[v]]]=cnt;
shenghui[cnt]=v;
}
}
sta[v][++top[v]]=v;
for (;top[v];top[v]--) sta[fa[v]][++top[fa[v]]]=sta[v][top[v]];
}
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&B);
int i,x,y;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);
}
dfs(1);
for (;top[0];top[0]--) belong[sta[0][top[0]]]=cnt;
if (cnt==0) {printf("0\n");return 0;}
printf("%d\n",cnt);
for (i=1;i<=n;i++) printf("%d ",belong[i]);ln;
for (i=1;i<=cnt;i++) printf("%d ",shenghui[i]);ln;
return 0;
}
Problem1087
#include<cstdio>
using namespace std;
typedef long long LL;
LL f[100][10][1999];
int n,K;
bool pan1(int x)
{
if (x&(x>>1)) return false;
//if (x&(x>>2)) return false;
if (x&(x<<1)) return false;
//if (x&(x<<2)) return false;
return true;
}
bool pan2(int x,int y)
{
if (x&y) return false;
if (x&(y>>1)) return false;
//if (x&(y>>2)) return false;
if (x&(y<<1)) return false;
//if (x&(y<<2)) return false;
return true;
}
int calc(int x)
{
int res=0;
for (;x;x-=x&-x) res++;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&K);
int mm=(1<<n)-1;
f[0][0][0]=1;
int i,j,k,l;
for (i=1;i<=K;i++)
for (j=1;j<=n;j++)
for (k=0;k<=mm;k++)
{
if (!pan1(k)||calc(k)>i) continue;
for (l=0;l<=mm;l++)
{
if (!pan1(l)||calc(k)+calc(l)>i) continue;
if (!pan2(k,l)) continue;
f[i][j][k]+=f[i-calc(k)][j-1][l];
}
//printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
}
LL ans=0;
for (j=1;j<=n;j++)
for (k=0;k<=mm;k++) ans+=f[K][j][k];
printf("%lld\n",ans);
return 0;
}Problem1088
#include<cstdio>
using namespace std;
const int NN=20005;
int a[NN],b[NN],n;
bool check(int x,int y)
{
if (x+y!=a[1]) return false;
b[1]=x,b[2]=y;
for (int i=2;i<n;i++)
{
if (b[i-1]+b[i]>a[i]) return false;
b[i+1]=a[i]-b[i-1]-b[i];
}
if (b[n-1]+b[n]!=a[n]) return false;
return true;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
if (n==1) {printf("1\n");return 0;}
int ans=0;
if (check(0,0)) ans++;
if (check(1,0)) ans++;
if (check(1,1)) ans++;
if (check(0,1)) ans++;
printf("%d\n",ans);
return 0;
}Problem1090
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define p1 255
#define mo 10007
#define p2 19980723
#define NN 111
#define ln printf("\n")
int mi1[NN],mi2[NN],h1[NN],h2[NN],f[NN][NN];
int n;
char s[NN];
bool qwe;
int hash1(int l,int r)
{
int len=r-l+1;
int tmp=(h1[r]-h1[l-1]*mi1[len])%mo;
if (tmp<0) tmp+=mo;
return tmp;
}
int hash2(int l,int r)
{
int len=r-l+1;
return h2[r]-h2[l-1]*mi2[len];
}
bool check(int l,int k,int r)
{
int len=k-l+1;
int t1=hash1(l,k),t2=hash2(l,k);
int now=k+1;
while (now<=r)
{
int t3=hash1(now,now+len-1);
int t4=hash2(now,now+len-1);
if (t1!=t3||t2!=t4) return false;
now+=len;
}
return true;
}
int calc(int x)
{
int res=0;
for (;x;x/=10) res++;
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
//printf("n=%d\n",n);
int i,j,k,len;
for (mi1[0]=mi2[0]=1,i=1;i<=n;i++)
{
mi1[i]=mi1[i-1]*p1%mo;
h1[i]=(h1[i-1]+s[i]*mi1[i])%mo;
mi2[i]=mi2[i-1]*p2;
h2[i]=h2[i-1]+s[i]*mi2[i];
}
//printf("%d %d\n",hash1(20,22),hash1(23,25));
for (i=1;i<=n;i++) f[i][i]=1;
for (len=2;len<=n;len++)
for (i=1;i+len-1<=n;i++)
{
if (i==20&&len==9) qwe=true;
j=i+len-1;
f[i][j]=len;
for (k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for (k=i;k<j;k++)
if (len%(k-i+1)==0&&check(i,k,j))
{
f[i][j]=min(f[i][j],f[i][k]+2+calc(len/(k-i+1)));
//if (qwe) printf("true\n");
}
qwe=false;
}
//printf("f[20][28]=%d\n",f[20][28]);
//ln;ln;
printf("%d\n",f[1][n]);
return 0;
}
Problem1093
#include<cstdio>
#include<cstring>
using namespace std;
#define ln printf("\n")
#define mii(a,b) ((a)<(b)?(a):(b))
const int NN=101111,MM=1001111;
int aa[MM][2],o[NN],low[NN],dfn[NN],sta[NN],num[NN],belong[NN],du[NN],f[NN],g[NN],b[NN],flag[NN];
int n,m,mo,tot=1,TIME,top,scc;
bool vt[NN];
void out(int *a,int l,int r){for(int i=l;i<=r;i++)printf("%d ",a[i]);ln;}
struct edge
{
int a,b;
} e[MM];
void dfs(int v)
{
vt[v]=true;
dfn[v]=low[v]=++TIME;
sta[++top]=v;
for (int p=o[v];p;p=aa[p][0])
{
int y=aa[p][1];
if (!vt[y])
{
dfs(y);
low[v]=mii(low[v],low[y]);
}
else if (!belong[y]) low[v]=mii(low[v],dfn[y]);
}
if (low[v]==dfn[v])
{
scc++;
int k;
do
{
k=sta[top--];
belong[k]=scc;
num[scc]++;
} while (k!=v);
}
}
void addedge(int p,int q) {tot++;aa[tot][1]=q;aa[tot][0]=o[p];o[p]=tot;}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&m,&mo);
int i;
for (i=1;i<=m;i++)
{
scanf("%d%d",&e[i].a,&e[i].b);
addedge(e[i].a,e[i].b);
}
for (i=1;i<=n;i++)
if (!vt[i]) dfs(i);
//printf("dfn ");out(dfn,1,n);printf("low ");out(low,1,n);printf("belong ");out(belong,1,n);
memset(o,0,sizeof(o));tot=1;
for (i=1;i<=m;i++)
if (belong[e[i].a]!=belong[e[i].b])
addedge(belong[e[i].a],belong[e[i].b]),du[belong[e[i].b]]++;
n=scc;
for (top=0,i=1;i<=n;i++)
if (du[i]==0) sta[++top]=i;
b[0]=0;
while (top)
{
b[++b[0]]=sta[top--];
for (int p=o[b[b[0]]];p;p=aa[p][0])
{
int y=aa[p][1];
du[y]--;
if (du[y]==0) sta[++top]=y;
}
}
for (i=n;i;i--)
{
int x=b[i];
f[x]=num[x],g[x]=1;
TIME++;
for (int p=o[x];p;p=aa[p][0])
{
int y=aa[p][1];
if (flag[y]==TIME) continue;else flag[y]=TIME;
if (f[y]+num[x]>f[x]) f[x]=f[y]+num[x],g[x]=g[y];
else if (f[y]+num[x]==f[x])
{
g[x]+=g[y];
if (g[x]>mo) g[x]-=mo;
}
}
}
int ans=0;
for (i=1;i<=n;i++)
if (f[i]>ans) ans=f[i];
int res=0;
for (i=1;i<=n;i++)
if (f[i]==ans)
{
res+=g[i];
if (res>mo) res-=mo;
}
printf("%d\n%d\n",ans,res);
return 0;
}Problem1094
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double DD;
typedef double dd;
#define ln printf("\n")
const DD eps=1e-9,dinf=1e30;
const DD pai=3.141592653589793238;
const int NN=111;
int n,K;
DD R,tim[NN][NN];
inline int dcmp(DD x)
{
if (fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct point
{
DD x,y;
point(DD a=0,DD b=0) {x=a;y=b;}
void in() {dd xx,yy;scanf("%lf%lf",&xx,&yy);x=xx,y=yy;}
void out() {printf("%.2f %.2f ",(dd)x,(dd)y);}
DD len() {return sqrt(x*x+y*y);}
friend DD dis(point a,point b) {return (a-b).len();}
point rotate(DD sita)
{
DD xx=x*cos(sita)-y*sin(sita);
DD yy=y*cos(sita)+x*sin(sita);
x=xx,y=yy;
return *this;
}
friend point operator +(point a,point b) {return point(a.x+b.x,a.y+b.y);}
friend point operator -(point a,point b) {return point(a.x-b.x,a.y-b.y);}
friend point operator *(DD t,point a) {return point(a.x*t,a.y*t);}
friend point operator *(point a,DD t) {return point(a.x*t,a.y*t);}
friend point operator /(point a,DD t) {return point(a.x/t,a.y/t);}
friend DD operator %(point a,point b) {return a.x*b.y-b.x*a.y;}
friend DD operator *(point a,point b) {return a.x*b.x+a.y*b.y;}
friend DD operator ^(point a,point b)
{
DD t=a*b/(a.len()*b.len());
if (t>1) t=1;if (t<-1) t=-1;
return acos(t);
}
} O,V[NN][NN],pos[NN][NN];
struct line
{
point P,v;
void out() {P.out();v.out();ln;}
line(point A=point(0,0),point B=point(0,0)) {P=A;v=B;}
};
point getjdwithC(point P,point v)
{
DD m=P.x-O.x,n=P.y-O.y,x=v.x,y=v.y;
DD A=x*x+y*y,B=2*m*x+2*n*y,C=m*m+n*n-R*R;
DD tmp=sqrt(B*B-4*A*C);
DD t1=(-B+tmp)/(2*A),t2=(-B-tmp)/(2*A);
return P+max(t1,t2)*v;
}
void work(point *pos,DD *tim,point *V,DD x0,DD y0,DD vx0,DD vy0)
{
pos[0]=point(x0,y0);
tim[0]=0;
V[0]=point(vx0,vy0);
point M=point(x0,y0),v=point(vx0,vy0);
DD vv=v.len();
for (int i=1;i<=K;i++)
{
point N=getjdwithC(M,v);
pos[i]=N;
tim[i]=tim[i-1]+(N-M).len()/vv;
DD sita=(M-N)^(O-N);
v=-1*v;
if (dcmp((O-N)%(M-N))<0) v.rotate(sita*2);
else v.rotate(-sita*2);
V[i]=v;
M=N;
}
}
line find(point *pos,DD *tim,point *V,int &now,DD st)
{
for (;now<K;now++)
{
if (st-tim[now+1]>-eps) continue;
point P=pos[now],v=V[now];
return line(P+(st-tim[now])*v,v);
}
return line(point(0,0),point(0,0));
}
point linejd(point P,point v,point Q,point w)
{
point u=P-Q;
DD t=(w%u)/(v%w);
return P+t*v;
}
DD finddist(point P,point A,point B)
{
DD x=(A-B).x,y=(A-B).y;
point O=linejd(A,B-A,P,point(-y,x));
if (dcmp(dis(O,A)+dis(O,B)-dis(A,B))==0) return dis(P,O);
return min(dis(P,A),dis(P,B));
}
DD mindist(line l1,line l2,DD T)
{
point A=l1.P,v1=l1.v,B=l2.P,v2=l2.v;
if (fabs(T)<eps) return dis(A,B);
point M=A-B,N=M+(v1-v2)*T;
return finddist(point(0,0),M,N);
}
DD calc(point *pos1,DD *tim1,point *V1,point *pos2,DD *tim2,point *V2)
{
static DD b[NN<<1];
int cnt=0,i;
for (i=0;i<=K;i++)
b[++cnt]=tim1[i],b[++cnt]=tim2[i];
sort(b+1,b+cnt+1);
int t=1;
for (i=2;i<=cnt;i++)
if (dcmp(b[i]-b[t])!=0) b[++t]=b[i];
cnt=t;
int now1=0,now2=0;
DD res=dinf;
for (i=1;i<=cnt;i++)
{
line t1=find(pos1,tim1,V1,now1,b[i-1]);
line t2=find(pos2,tim2,V2,now2,b[i-1]);
if (now1==K||now2==K) break;
res=min(res,mindist(t1,t2,b[i]-b[i-1]));
}
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
O.in();
dd xx;
scanf("%lf%d%d",&xx,&n,&K);
R=xx;
int i,j;
for (i=1;i<=n;i++)
{
dd a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
work(pos[i],tim[i],V[i],a,b,c,d);
}
DD ans=dinf;
for (i=1;i<n;i++) for (j=i+1;j<=n;j++)
ans=min(ans,calc(pos[i],tim[i],V[i],pos[j],tim[j],V[j]));
printf("%.3f\n",(dd)ans);
return 0;
}Problem1094
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double DD;
typedef double dd;
#define ln printf("\n")
const DD eps=1e-9,dinf=1e30;
const DD pai=3.14159265358979;
const int NN=111;
int n,K;
DD R,tim[NN][NN];
inline int dcmp(DD x)
{
if (fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct point
{
DD x,y;
point(DD a=0,DD b=0) {x=a;y=b;}
void in() {dd xx,yy;scanf("%lf%lf",&xx,&yy);x=xx,y=yy;}
void out() {printf("%.2f %.2f ",(dd)x,(dd)y);}
DD len() {return sqrt(x*x+y*y);}
friend DD dis(point a,point b) {return (a-b).len();}
point rotate(DD sita)
{
DD xx=x*cos(sita)-y*sin(sita);
DD yy=y*cos(sita)+x*sin(sita);
x=xx,y=yy;
return *this;
}
friend point operator +(point a,point b) {return point(a.x+b.x,a.y+b.y);}
friend point operator -(point a,point b) {return point(a.x-b.x,a.y-b.y);}
friend point operator *(DD t,point a) {return point(a.x*t,a.y*t);}
friend point operator *(point a,DD t) {return point(a.x*t,a.y*t);}
friend point operator /(point a,DD t) {return point(a.x/t,a.y/t);}
friend DD operator %(point a,point b) {return a.x*b.y-b.x*a.y;}
friend DD operator *(point a,point b) {return a.x*b.x+a.y*b.y;}
friend DD operator ^(point a,point b)
{
DD t=a*b/(a.len()*b.len());
if (t>1) t=1;if (t<-1) t=-1;
return acos(t);
}
} O,V[NN][NN],pos[NN][NN];
struct line
{
point P,v;
void out() {P.out();v.out();ln;}
line(point A=point(0,0),point B=point(0,0)) {P=A;v=B;}
};
point getjdwithC(point P,point v)
{
DD m=P.x-O.x,n=P.y-O.y,x=v.x,y=v.y;
DD A=x*x+y*y,B=2*m*x+2*n*y,C=m*m+n*n-R*R;
DD tmp=sqrt(B*B-4*A*C);
DD t1=(-B+tmp)/(2*A),t2=(-B-tmp)/(2*A);
return P+max(t1,t2)*v;
}
void work(point *pos,DD *tim,point *V,DD x0,DD y0,DD vx0,DD vy0)
{
pos[0]=point(x0,y0);
tim[0]=0;
V[0]=point(vx0,vy0);
point M=point(x0,y0),v=point(vx0,vy0);
DD vv=v.len();
for (int i=1;i<=K;i++)
{
point N=getjdwithC(M,v);
pos[i]=N;
tim[i]=tim[i-1]+(N-M).len()/vv;
DD sita=(M-N)^(O-N);
v=-1*v;
if (dcmp((O-N)%(M-N))<0) v.rotate(sita*2);
else v.rotate(-sita*2);
V[i]=v;
M=N;
}
}
line find(point *pos,DD *tim,point *V,int &now,DD st)
{
for (;now<K;now++)
{
if (st-tim[now+1]>-eps) continue;
point P=pos[now],v=V[now];
return line(P+(st-tim[now])*v,v);
}
return line(point(0,0),point(0,0));
}
point linejd(point P,point v,point Q,point w)
{
point u=P-Q;
DD t=(w%u)/(v%w);
return P+t*v;
}
DD finddist(point P,point A,point B)
{
DD x=(A-B).x,y=(A-B).y;
point O=linejd(A,B-A,P,(A-B).rotate(pai/2));
if (dcmp(dis(O,A)+dis(O,B)-dis(A,B))==0) return dis(P,O);
return min(dis(P,A),dis(P,B));
}
DD mindist(line l1,line l2,DD T)
{
point A=l1.P,v1=l1.v,B=l2.P,v2=l2.v;
if (fabs(T)<eps) return dis(A,B);
point M=A-B,N=M+(v1-v2)*T;
return finddist(point(0,0),M,N);
}
DD calc(point *pos1,DD *tim1,point *V1,point *pos2,DD *tim2,point *V2)
{
static DD b[NN<<1];
int cnt=0,i;
for (i=0;i<=K;i++)
b[++cnt]=tim1[i],b[++cnt]=tim2[i];
sort(b+1,b+cnt+1);
int t=1;
for (i=2;i<=cnt;i++)
if (dcmp(b[i]-b[t])!=0) b[++t]=b[i];
cnt=t;
int now1=0,now2=0;
DD res=dinf;
for (i=1;i<=cnt;i++)
{
line t1=find(pos1,tim1,V1,now1,b[i-1]);
line t2=find(pos2,tim2,V2,now2,b[i-1]);
if (now1==K||now2==K) break;
res=min(res,mindist(t1,t2,b[i]-b[i-1]));
}
return res;
}
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
O.in();
dd xx;
scanf("%lf%d%d",&xx,&n,&K);
R=xx;
int i,j;
for (i=1;i<=n;i++)
{
dd a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
work(pos[i],tim[i],V[i],a,b,c,d);
}
DD ans=dinf;
for (i=1;i<n;i++) for (j=i+1;j<=n;j++)
ans=min(ans,calc(pos[i],tim[i],V[i],pos[j],tim[j],V[j]));
printf("%.3f\n",(dd)ans);
return 0;
}
