#define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; struct { int fr,to,nxt; Node(){} Node(int _f,int_t,int _n):fr(_f),to(_t),nxt(_n) {} }; int op[6][3]={{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}; Node a[200005]; int head[100005]; ll v[100005][3]; vector<int>ve; int du[100005]; int Ans[100005],Tmp[100005]; voidbuild(int o,int fr,int to){ a[o]=Node(fr,to,head[fr]); head[fr]=o; du[fr]++; } voidsolve(){ ve.clear(); int n; scanf("%d",&n); MS(v,0); MS(head,-1); for (int i=0;i<3;i++){ for (int j=1;j<=n;j++) scanf("%lld",&v[j][i]); } for (int i=0;i<n-1;i++){ int fr,to; scanf("%d%d",&fr,&to); build(i<<1,fr,to); build(i<<1|1,to,fr); } int fa=0,now; for (int i=1;i<=n;i++){ if (du[i]>2){ printf("-1n"); return; } elseif (du[i]==1) now=i; } int m=n; while (m--){ ve.push_back(now); for (int i=head[now];i!=-1;i=a[i].nxt){ int p=a[i].to; if (p==fa) continue; fa=now; now=p; break; } } int si=ve.size(); ll ans=LLONG_MAX; for (int i=0;i<6;i++){ int p=0; ll tmp=0; for (int j=0;j<si;j++){ tmp+=v[ve[j]][op[i][p]-1]; Tmp[ve[j]]=op[i][p]; p++; p%=3; } if (tmp<ans){ for (int j=1;j<=n;j++) Ans[j]=Tmp[j]; ans=tmp; } } printf("%lldn",ans); for (int i=1;i<=n;i++) printf("%d ",Ans[i]); printf("n"); } intmain(){ solve(); return0; }
#define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; char s[505]; intjudge(int n){ int tmp=0,mtmp=0,op=0; for (int i=0;i<n;i++){ if (s[i]=='(') tmp++; else tmp--; if (tmp<mtmp){ op=i+1; mtmp=tmp; } } int ans=0; for (int i=0;i<n;i++){ int p=(op+i)%n; if (s[p]=='(') tmp++; else tmp--; if (tmp==0) ans++; } return ans; } voidsolve(){ int n; scanf("%d%s",&n,s); int tmp=0; for (int i=0;i<n;i++){ if (s[i]=='(') tmp++; else tmp--; } if (tmp!=0){ printf("0n1 1n"); return; } pair<int,int>ans=MP(1,1); int Ans=judge(n); for (int i=0;i<n;i++){ if (s[i]=='('){ for (int j=0;j<n;j++){ if (s[j]==')'){ swap(s[i],s[j]); int t=judge(n); if (t>Ans){ Ans=t; ans=MP(i+1,j+1); } swap(s[i],s[j]); } } } } printf("%dn%d %dn",Ans,ans.fi,ans.se); } intmain(){ solve(); return0; }
#define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; struct { int l,r,pos; bool flag; booloperator<(const Node &A)const { return r>A.r; } }; Node a[205]; int b[205]; vector<int>Ans; voidsolve(){ Ans.clear(); int n,k; scanf("%d%d",&n,&k); for (int i=0;i<n;i++){ scanf("%d%d",&a[i].l,&a[i].r); a[i].pos=i+1; a[i].flag=true; for (int j=a[i].l;j<=a[i].r;j++) b[j]++; } sort(a,a+n); for (int i=1;i<=200;i++){ if (b[i]>k){ int num=b[i]-k; for (int j=0;j<n;j++){ if (num==0) break; if (a[j].flag&&a[j].l<=i&&a[j].r>=i){ a[j].flag=false; for (int k=a[j].l;k<=a[j].r;k++) b[k]--; num--; Ans.push_back(a[j].pos); } } } } int ans=Ans.size(); printf("%dn",ans); for (auto k:Ans) printf("%d ",k); printf("n"); } intmain(){ solve(); return0; }
#include<bits/stdc++.h> #define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; voidsolve(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if (c<a) swap(a,c); int ans; if (a>=(b+c+1)/2) ans=a; elseif (a+b<=(c+1)/2) ans=(c+1)/2; else ans=(a+b+c+2)/3; printf("%dn",ans); } intmain(){ int t; scanf("%d",&t); while (t--) solve(); return0; }
#include<bits/stdc++.h> #define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; struct { ll p; bool vis; int m; booloperator<(Node &A)const { return m<A.m; } }; Node a[5005]; voidsolve(){ int n; scanf("%d",&n); for (int i=0;i<n;i++){ scanf("%d%lld",&a[i].m,&a[i].p); a[i].vis=false; } sort(a,a+n); ll ans=0; int now=0; for (int i=0;i<n;i++){ if (a[i].vis) continue; if (now<a[i].m){ while (now<a[i].m){ int num=now; int t=i; for (int j=i;j<n;j++){ if (a[j].vis) continue; if (a[j].m>num||a[j].p<a[t].p) t=j; num++; } a[t].vis=true; now++; ans+=a[t].p; } if (a[i].vis) continue; } now++; a[i].vis=true; } printf("%lldn",ans); } intmain(){ int t; scanf("%d",&t); while (t--) solve(); return0; }
#include<bits/stdc++.h> #define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; int a[2][100005],b[2][100005]; voidsolve(){ int n,q; scanf("%d%d",&n,&q); for (int i=0;i<2;i++){ for (int j=1;j<=n;j++){ scanf("%d",&a[i][j]); b[i][j]=b[i][j-1]+a[i][j]%2; } } while (q--){ int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int x=min(x1,x2),xx=max(x1,x2); int y=min(y1,y2),yy=max(y1,y2); int ansx=b[0][xx]-b[0][x-1],ansy=b[1][yy]-b[1][y-1]; if ((ansx==0&&ansy==0)||(ansx==xx-x+1&&ansy==yy-y+1)) printf("YESn"); else printf("NOn"); } } intmain(){ solve(); return0; }
#include<bits/stdc++.h> #define ll long long #define MS(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define Ls o<<1 #define Rs o<<1|1 #define MID (r-l)/2+l #define MP(a,b) make_pair(a,b) usingnamespacestd; structEdge { int fr,to,nxt; Edge(){} Edge(int _f,int_t,int _n):fr(_f),to(_t),nxt(_n) {} }; Edge a[300005]; int head[300005]; voidbuild(int o,int fr,int to){ a[o]=Edge(fr,to,head[fr]); head[fr]=o; } int ans[300005],sum[300005],fa[300005]; voiddfs(int o){ sum[o]=1; for (int i=head[o];i!=-1;i=a[i].nxt){ int p=a[i].to; fa[p]=o; dfs(p); sum[o]+=sum[p]; } ans[o]=o; for (int i=head[o];i!=-1;i=a[i].nxt){ int p=a[i].to; if (sum[p]*2>sum[o]) ans[o]=ans[p]; } while ((sum[o]-sum[ans[o]])*2>sum[o]) ans[o]=fa[ans[o]]; } voidsolve(){ int n,q; MS(head,-1); scanf("%d%d",&n,&q); for (int i=2;i<=n;i++){ int fr; scanf("%d",&fr); build(i-2,fr,i); } dfs(1); while (q--){ int t; scanf("%d",&t); printf("%dn",ans[t]); } } intmain(){ solve(); return0; }
近期评论