JOI春合宿 参加記
コンテスト中のことをいちいち書くのは面倒なのでコードだけ張ります。
Day1
- Bus 100/100
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<map> using namespace std; vector<int>pat[600000]; typedef pair<int,int>pii; typedef pair<pii,pii>pi4; vector<int>tim[100000]; bool flag[600000]; int ans[600000]; int bpt[100000]; int now=-1; int la,lb,ba,bb; void dfs(int node) { if(flag[node]) { return; } flag[node]=true; //printf("%d\n",node); if(node<=bb&&now<node) { now=node; } for(int i=0;i<pat[node].size();i++) { dfs(pat[node][i]); } } int main() { int num,way; scanf("%d%d",&num,&way); vector<pi4>zv; for(int i=0;i<way;i++) { int za,zb,zc,zd; scanf("%d%d%d%d",&za,&zb,&zc,&zd); za--; zb--; zv.push_back(make_pair(make_pair(za,zb),make_pair(zc,zd))); tim[za].push_back(zc); tim[zb].push_back(zd); } int pt=0; for(int i=0;i<num;i++) { sort(tim[i].begin(),tim[i].end()); bpt[i]=pt; for(int j=0;j<tim[i].size();j++) { //printf("%d %d %d\n",i,tim[i][j],pt); pt++; if(j!=0) { pat[pt-1].push_back(pt-2); } } } for(int i=0;i<zv.size();i++) { int wa=lower_bound(tim[zv[i].first.second].begin(),tim[zv[i].first.second].end(),zv[i].second.second)-tim[zv[i].first.second].begin()+bpt[zv[i].first.second]; int wb=lower_bound(tim[zv[i].first.first].begin(),tim[zv[i].first.first].end(),zv[i].second.first)-tim[zv[i].first.first].begin()+bpt[zv[i].first.first]; pat[wa].push_back(wb); //printf("path: %d %d\n",wa,wb); } la=pt-tim[num-1].size(),lb=pt-1; ba=0,bb=tim[0].size()-1; fill(flag,flag+pt,false); for(int i=la;i<=lb;i++) { //printf("case: %d\n",i); dfs(i); if(now==-1) { ans[i]=-1; } else { ans[i]=tim[0][now]; } } int query; scanf("%d",&query); for(int p=0;p<query;p++) { int zan; scanf("%d",&zan); int upp=upper_bound(tim[num-1].begin(),tim[num-1].end(),zan)-tim[num-1].begin()-1; if(upp==-1) { printf("-1\n"); } else { printf("%d\n",ans[upp+la]); } } }
- Growing 100/100
#include<stdio.h> #include<vector> #include<algorithm> #include<map> using namespace std; #define SIZE 524288 typedef long long ll; typedef pair<ll,ll>pii; class BIT { public: ll bit[SIZE+1]; void update(int a,ll b) { for(;;) { if(a>SIZE) { break; } bit[a]+=b; a+=a&-a; } } ll get(int a) { ll ret=0; for(;;) { if(a<=0) { break; } ret+=bit[a]; a-=a&-a; } return ret; } }; BIT bi; int main() { int num; scanf("%d",&num); vector<int>vec,zv; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); zv.push_back(zan); } sort(zv.begin(),zv.end()); map<int,vector<int> >ma; for(int i=0;i<num;i++) { vec[i]=lower_bound(zv.begin(),zv.end(),vec[i])-zv.begin()+1; ma[vec[i]].push_back(i); } ll ans=0; map<int,vector<int> >::iterator it=ma.begin(); for(;;) { if(it==ma.end()) { break; } vector<int>v=(*it).second; for(int i=0;i<v.size();i++) { int ban=v[i]+bi.get(v[i]+1); //printf("%d %d\n",v[i],ban); ans+=min(ban,num+int(bi.get(SIZE))-1-ban-(int(v.size())-i-1)); //printf("%d\n",ans); bi.update(v[i]+1,-1); } it++; } printf("%lld\n",ans); }
- Historical 40/100
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef long long ll; ll rui[5000][5001]; typedef pair<ll,ll>pii; typedef pair<pii,ll>pi3; int toseg[100000]; ll ans[100000]; #define SIZE 131072 class segtree { public: ll seg[SIZE*2]; void update(int a,ll b) { a+=SIZE; seg[a]+=b; for(;;) { if(a==0) { return; } a/=2; seg[a]=max(seg[a*2],seg[a*2+1]); } } ll get(int beg,int end,int node,int lb,int ub) { if(ub<beg||end<lb) { return 0; } if(beg<=lb&&ub<=end) { return seg[node]; } return max(get(beg,end,node*2,lb,(lb+ub)/2),get(beg,end,node*2+1,(lb+ub)/2+1,ub)); } }; segtree tree; vector<int>uni(vector<int>vec) { sort(vec.begin(),vec.end()); vector<int>ret; int now=-1; for(int i=0;i<vec.size();i++) { if(now!=vec[i]) { now=vec[i]; ret.push_back(now); } } return ret; } int main() { int num,query; scanf("%d%d",&num,&query); if(num<=5000&&query<=5000) //if(false) { vector<int>vec,zv; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); } zv=uni(vec); for(int i=0;i<vec.size();i++) { int low=lower_bound(zv.begin(),zv.end(),vec[i])-zv.begin(); rui[low][i+1]++; } for(int i=0;i<zv.size();i++) { for(int j=0;j<vec.size();j++) { rui[i][j+1]+=rui[i][j]; } } for(int p=0;p<query;p++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; ll maxi=0; for(int i=0;i<zv.size();i++) { maxi=max(maxi,(rui[i][zb+1]-rui[i][za])*zv[i]); } printf("%lld\n",maxi); } } else { vector<int>vec,zv; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); } zv=uni(vec); for(int i=0;i<num;i++) { toseg[i]=lower_bound(zv.begin(),zv.end(),vec[i])-zv.begin(); } vector<pi3>qu; for(int i=0;i<query;i++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; qu.push_back(make_pair(make_pair(za,zb),i)); } sort(qu.begin(),qu.end()); int beg=0,end=0; for(int i=0;i<query;i++) { for(;beg<qu[i].first.first;beg++) { tree.update(toseg[beg],-vec[beg]); } for(;end<=qu[i].first.second;end++) { tree.update(toseg[end],vec[end]); } ans[qu[i].second]=tree.seg[1]; } for(int i=0;i<query;i++) { printf("%lld\n",ans[i]); } } }
- Ramen 100/100
#include "ramen.h" #include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int>ra,rb; void Ramen(int num) { if(num%2==1) { ra.push_back(num-1); rb.push_back(num-1); } for(int i=0;i<num-1;i+=2) { if(Compare(i,i+1)==-1) { ra.push_back(i); rb.push_back(i+1); } else { ra.push_back(i+1); rb.push_back(i); } } int na=ra[0],nb=rb[0]; for(int i=1;i<ra.size();i++) { if(Compare(na,ra[i])!=-1) { na=ra[i]; } } for(int i=1;i<rb.size();i++) { if(Compare(nb,rb[i])!=1) { nb=rb[i]; } } Answer(na,nb); }
Day2
Bottle 100/100
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> using namespace std; int map[2002][2002]; typedef pair<int,int>pii; typedef pair<int,pii>pi3; typedef pair<pii,pii>pi4; int dist[2002][2002]; int frm[2002][2002]; vector<pi3>roa; vector<pii>pat[200000]; vector<pii>ko[200000]; bool flag[200000]; bool vis[2002][2002]; int par[20][200000]; int cst[20][200000]; int depth[200000]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; class unionfind { public: int par[200000]; int ran[200000]; int ren[200000]; void init() { for(int i=0;i<200000;i++) { par[i]=i; ran[i]=0; ren[i]=1; } } int find(int a) { if(a==par[a]) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; ren[a]+=ren[b]; } else { par[a]=b; ren[b]+=ren[a]; } if(ran[a]==ran[b]) { ran[b]++; } } }; unionfind uf; void dfs(int node,int d) { if(flag[node]) { return; } flag[node]=true; depth[node]=d; for(int i=0;i<pat[node].size();i++) { if(!flag[pat[node][i].first]) { ko[node].push_back(pat[node][i]); dfs(pat[node][i].first,d+1); } } } int num; void lcainit() { for(int i=0;i<20;i++) { for(int j=0;j<num;j++) { par[i][j]=-1; } } for(int i=0;i<num;i++) { for(int j=0;j<ko[i].size();j++) { par[0][ko[i][j].first]=i; cst[0][ko[i][j].first]=ko[i][j].second; } } for(int i=1;i<20;i++) { for(int j=0;j<num;j++) { if(par[i-1][j]!=-1) { par[i][j]=par[i-1][par[i-1][j]]; cst[i][j]=max(cst[i-1][j],cst[i-1][par[i-1][j]]); } else { par[i][j]=par[i-1][j]; cst[i][j]=cst[i-1][j]; } } } } int lca(int a,int b) { if(depth[a]>depth[b]) { swap(a,b); } int ret=0; for(int i=19;i>=0;i--) { if(depth[b]-(1<<i)>=depth[a]) { ret=max(ret,cst[i][b]); b=par[i][b]; } } if(a==b) { return ret; } for(int i=19;i>=0;i--) { if(par[i][a]!=par[i][b]) { ret=max(ret,max(cst[i][a],cst[i][b])); a=par[i][a]; b=par[i][b]; } } return max(ret,max(cst[0][a],cst[0][b])); } int main() { int mx,my,query; scanf("%d%d%d%d",&mx,&my,&num,&query); for(int i=0;i<2002;i++) { for(int j=0;j<2002;j++) { map[i][j]=-2; vis[i][j]=false; dist[i][j]=1000000000; } } for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { char zan; scanf(" %c",&zan); if(zan=='.') { map[i+1][j+1]=-1; } } } vector<pii>vec; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; vec.push_back(make_pair(za+1,zb+1)); map[za+1][zb+1]=i; } uf.init(); queue<pi4>que; for(int p=0;p<num;p++) { que.push(make_pair(make_pair(0,p),vec[p])); } for(;;) { if(que.empty()) { break; } pi4 zan=que.front(); que.pop(); int x=zan.second.first,y=zan.second.second; int d=zan.first.first,f=zan.first.second; if(vis[x][y]) { continue; } vis[x][y]=true; dist[x][y]=d; frm[x][y]=f; for(int i=0;i<4;i++) { if(map[x+dx[i]][y+dy[i]]!=-2) { que.push(make_pair(make_pair(d+1,f),make_pair(x+dx[i],y+dy[i]))); } } } for(int i=0;i<=mx+1;i++) { for(int j=0;j<my+1;j++) { if(frm[i][j]!=frm[i][j+1]&&map[i][j]!=-2&&map[i][j+1]!=-2) { roa.push_back(make_pair(dist[i][j]+dist[i][j+1],make_pair(frm[i][j],frm[i][j+1]))); } } } for(int i=0;i<mx+1;i++) { for(int j=0;j<=my+1;j++) { if(frm[i][j]!=frm[i+1][j]&&map[i][j]!=-2&&map[i+1][j]!=-2) { roa.push_back(make_pair(dist[i][j]+dist[i+1][j],make_pair(frm[i][j],frm[i+1][j]))); } } } sort(roa.begin(),roa.end()); for(int i=0;i<roa.size();i++) { if(uf.find(roa[i].second.first)!=uf.find(roa[i].second.second)) { pat[roa[i].second.first].push_back(make_pair(roa[i].second.second,roa[i].first)); pat[roa[i].second.second].push_back(make_pair(roa[i].second.first,roa[i].first)); uf.unite(roa[i].second.first,roa[i].second.second); } } fill(flag,flag+200000,false); for(int i=0;i<num;i++) { dfs(i,0); }/* for(int i=0;i<num;i++) { for(int j=0;j<ko[i].size();j++) { printf("%d %d %d\n",i+1,ko[i][j].first+1,ko[i][j].second); } }*/ lcainit(); for(int p=0;p<query;p++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; if(uf.find(za)!=uf.find(zb)) { printf("-1\n"); } else { printf("%d\n",lca(za,zb)); } } }
Collecting 100/100
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; class unionfind { public: int par[100000]; int ran[100000]; ll ren[100000]; void init() { for(int i=0;i<100000;i++) { par[i]=i; ran[i]=0; ren[i]=1; } } int find(int a) { if(a==par[a]) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; ren[a]+=ren[b]; } else { par[a]=b; ren[b]+=ren[a]; } if(ran[a]==ran[b]) { ran[b]++; } } }; unionfind uf; vector<int>pat[100000]; bool flag[100000]; void dfs(int node,int p) { uf.unite(node,p); //printf("%d %d\n",node+1,p+1); if(flag[node]) { return; } flag[node]=true; for(int i=0;i<pat[node].size();i++) { dfs(pat[node][i],p); } } int main() { int num,way; scanf("%d%d",&num,&way); for(int i=0;i<way;i++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; pat[za].push_back(zb); } uf.init(); fill(flag,flag+100000,false); for(int i=0;i<num;i++) { if(pat[i].size()>=2) { for(int j=0;j<pat[i].size();j++) { dfs(pat[i][j],pat[i][0]); } } } ll ans=way; for(int i=0;i<num;i++) { if(uf.find(i)==i) { ans+=(uf.ren[i])*(uf.ren[i]-1); } } for(int i=0;i<num;i++) { for(int j=0;j<pat[i].size();j++) { if(uf.find(i)==uf.find(pat[i][j])) { ans--; } } } printf("%lld\n",ans); }
Stamps 100/100
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll dp[3002][3004]; vector<ll>u1,d1,u2,d2; #define INF 1000000000000000000LL; int main() { int num; ll tim; scanf("%d%lld",&num,&tim); for(int i=0;i<num;i++) { int za,zb,zc,zd; scanf("%d%d%d%d",&za,&zb,&zc,&zd); u1.push_back(za); d1.push_back(zb); u2.push_back(zc); d2.push_back(zd); } for(int i=0;i<3002;i++) { for(int j=0;j<3004;j++) { dp[i][j]=INF; } } dp[0][1]=0; for(int i=0;i<num;i++) { vector<ll>vec1,vec2; for(int j=0;j<=num+2;j++) { vec1.push_back(dp[i][j]+tim*(j+j-1)-(u2[i]+d1[i])*j); vec2.push_back(dp[i][j]+tim*(j+j-1)+(u1[i]+d2[i])*j); } for(int j=1;j<=num+2;j++) { vec1[j]=min(vec1[j],vec1[j-1]); } for(int j=num+1;j>=0;j--) { vec2[j]=min(vec2[j],vec2[j+1]); } for(int k=1;k<=num+1;k++) { dp[i+1][k]=min(dp[i+1][k],vec2[k+1]-k*(u1[i]+d2[i])); dp[i+1][k]=min(dp[i+1][k],vec1[k-1]+k*(u2[i]+d1[i])); if(k==1) { dp[i+1][k]=min(dp[i+1][k],dp[i][k]+tim*(k+k-1)+(u1[i]+d1[i])); } else { dp[i+1][k]=min(dp[i+1][k],dp[i][k]+tim*(k+k-1)+min(u1[i]+d1[i],u2[i]+d2[i])); } }/* for(int k=1;k<=num+1;k++) { //printf("%d %d %lld\n",i,j,dp[i][j]); for(int j=1;j<=num+1;j++) { if(j>k) { dp[i+1][k]=min(dp[i+1][k],dp[i][j]+tim*(j+j-1)+(u1[i]+d2[i])*(j-k)); } if(j<k) { dp[i+1][k]=min(dp[i+1][k],dp[i][j]+tim*(j+j-1)+(u2[i]+d1[i])*(k-j)); } if(j==k) { if(j==1) { dp[i+1][k]=min(dp[i+1][k],dp[i][j]+tim*(j+j-1)+(u1[i]+d1[i])); } else { dp[i+1][k]=min(dp[i+1][k],dp[i][j]+tim*(j+j-1)+min(u1[i]+d1[i],u2[i]+d2[i])); } } } }*/ } //for(int i=1;i<=num;i++)for(int j=0;j<num+1;j++)printf("%d %d %lld\n",i,j,dp[i][j]); printf("%lld\n",dp[num][1]+tim); }
Day3
JOIOJI 100/100
#include<stdio.h> #include<vector> #include<algorithm> #include<map> #include<set> #include<string> #include<iostream> using namespace std; typedef pair<int,int>pii; int main() { int num; scanf("%d",&num); string str; cin>>str; int bj=0,bo=0,bi=0; map<pii,int>ma; set<pii>se; for(int i=0;i<num;i++) { if(se.find(make_pair(bo-bj,bi-bj))==se.end()) { ma[make_pair(bo-bj,bi-bj)]=i; se.insert(make_pair(bo-bj,bi-bj)); } if(str[i]=='J') { bj++; } if(str[i]=='O') { bo++; } if(str[i]=='I') { bi++; } } int maxi=0; int nj=0,no=0,ni=0; for(int i=num-1;i>=0;i--) { if(se.find(make_pair(bo-bj-(no-nj),bi-bj-(ni-nj)))!=se.end()) { maxi=max(maxi,i+1-ma[make_pair(bo-bj-(no-nj),bi-bj-(ni-nj))]); } if(str[i]=='J') { nj++; } if(str[i]=='O') { no++; } if(str[i]=='I') { ni++; } } printf("%d\n",maxi); }
Scarecrows 15/100(提出時のコードから変わっていますが提出時のコードはコメントアウトされています)
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<ll,pi2>pi3; #define SIZE 262144 int map[5001][5001]; class segtree { public: int seg[SIZE*2]; int segr[SIZE*2]; int segl[SIZE*2]; int flag[SIZE*2]; void update(int beg,int end,int node,int lb,int ub,int num) { if(ub<beg||end<lb) { return; } if(beg<=lb&&ub<=end) { seg[node]=1; segr[node]=num; segl[node]=num; flag[node]=num; return; } if(flag[node]) { seg[node*2]=1; seg[node*2+1]=1; segr[node*2]=num; segl[node*2]=num; segr[node*2+1]=num; segl[node*2+1]=num; flag[node*2]=num; flag[node*2+1]=num; flag[node]=0; } update(beg,end,node*2,lb,(lb+ub)/2); update(beg,end,node*2+1,(lb+ub)/2+1,ub); if(segr[node*2]==segl[node*2+1]) { seg[node]=seg[node*2]+seg[node*2+1]-1; } else { seg[node]=seg[node*2]+seg[node*2+1]; } segr[node]=segr[node*2+1]; segl[node]=segl[node*2]; } pi3 get(int beg,int end,int node,int lb,int ub) { if(beg<=lb&&ub<=end) { return make_pair(seg[node],make_pair(segl[node],segr[node])); } if(flag[node]) { seg[node*2]=1; seg[node*2+1]=1; segr[node*2]=num; segl[node*2]=num; segr[node*2+1]=num; segl[node*2+1]=num; flag[node*2]=num; flag[node*2+1]=num; flag[node]=0; } if(beg<=(lb+ub)/2&&(lb+ub)/2+1>=end) { pi3 za=get(beg,end,node*2,lb,(lb+ub)/2); pi3 zb=get(beg,end,node*2+1,(lb+ub)/2+1,ub); ll ret=0; if(za.second.second==zb.second.first) { ret=za.first+zb.first-1; } else { ret=za.first+zb.first; } return make_pair(ret,make_pair(za.second.first,zb.second.second)); } else { if(beg<=(lb+ub)/2) { return get(beg,end,node*2,lb,(lb+ub)/2); } else { return get(beg,end,node*2+1,(lb+ub)/2,ub); } } } }; segtree tree; int main() { int num; scanf("%d",&num); if(num>5000)return 0; vector<pii>vec; vector<ll>zx,zy; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); zx.push_back(za); zy.push_back(zb); vec.push_back(make_pair(za,zb)); } sort(zx.begin(),zx.end()); sort(zy.begin(),zy.end()); for(int i=0;i<num;i++) { vec[i].first=lower_bound(zx.begin(),zx.end(),vec[i].first)-zx.begin()+1; vec[i].second=lower_bound(zy.begin(),zy.end(),vec[i].second)-zy.begin()+1; } sort(vec.begin(),vec.end()); ll ret=0;/* for(int i=0;i<num;i++) { printf("%lld %lld\n",vec[i].first,vec[i].second); ret+=bi1.get(vec[i].second); ll pl=bi1.get(vec[i].second); bi1.update(vec[i].second,1-pl); bi2.update(vec[i].second,1); for(int j=0;j<num;j++) { printf("%lld ",bi1.get(j+1)); } printf("\n"); for(int j=0;j<num;j++) { printf("%lld ",bi2.get(j+1)); } printf("\n"); } printf("%lld\n",ret); } for(int i=0;i<num;i++) { map[vec[i].first][vec[i].second]++; } for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { map[i+1][j+1]+=map[i+1][j]+map[i][j+1]-map[i][j]; } } for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { if(vec[i].first<vec[j].first&&vec[i].second<vec[j].second) { if(map[vec[j].first][vec[j].second]-map[vec[i].first][vec[j].second]-map[vec[j].first][vec[i].second]+map[vec[i].first][vec[i].second]==1) { ret++; } } } } printf("%lld\n",ret); }*/ }
Voltage 100/100
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int>pat[100000]; vector<bool>isok[100000]; vector<int>ko[100000]; vector<int>back[100000]; bool flag[100000]; int par[100000]; int ord[100000]; int low[100000]; int depth[100000]; int imos[100000]; int lcapar[20][100000]; int ptord=0; typedef pair<int,int>pii; int col[100000]; bool dfs(int node,int d) { if(col[node]!=0&&col[node]!=d) { return false; } if(flag[node]) { return true; } flag[node]=true; col[node]=d; bool ret=true; for(int i=0;i<pat[node].size();i++) { if(isok) ret&=dfs(pat[node][i],-d); } return ret; } void dfs2(int node,int p,int d) { if(flag[node]) { return; } flag[node]=true; ord[node]=ptord++; depth[node]=d; int np=0; for(int i=0;i<pat[node].size();i++) { if(pat[node][i]==p&&np==0) { np++; continue; } if(!flag[pat[node][i]]) { ko[node].push_back(pat[node][i]); par[pat[node][i]]=node; dfs2(pat[node][i],node,d+1); } else { back[node].push_back(pat[node][i]); } } } int dfs3(int node) { int mini=ord[node]; for(int i=0;i<ko[node].size();i++) { mini=min(mini,dfs3(ko[node][i])); } for(int i=0;i<back[node].size();i++) { mini=min(mini,ord[back[node][i]]); } return low[node]=mini; } int dfs4(int node) { for(int i=0;i<ko[node].size();i++) { imos[node]+=dfs4(ko[node][i]); } return imos[node]; } int num,way; void lcainit() { for(int i=0;i<20;i++) { for(int j=0;j<num;j++) { lcapar[i][j]=-1; } } for(int i=0;i<num;i++) { lcapar[0][i]=par[i]; } for(int i=1;i<20;i++) { for(int j=0;j<num;j++) { if(lcapar[i-1][j]==-1) { lcapar[i][j]=-1; } else { lcapar[i][j]=lcapar[i-1][lcapar[i-1][j]]; } } } } int lca(int a,int b) { if(depth[a]>depth[b]) { swap(a,b); } for(int i=19;i>=0;i--) { if(depth[b]-(1<<i)>=depth[a]) { b=lcapar[i][b]; } } if(a==b) { return a; } for(int i=19;i>=0;i--) { if(lcapar[i][a]!=lcapar[i][b]) { a=lcapar[i][a]; b=lcapar[i][b]; } } return lcapar[0][a]; } int main() { scanf("%d%d",&num,&way); vector<pii>vec; for(int i=0;i<way;i++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; pat[za].push_back(zb); pat[zb].push_back(za); vec.push_back(make_pair(za,zb)); } bool isb=true; fill(flag,flag+100000,false); for(int i=0;i<num;i++) { if(!flag[i]) { isb&=dfs(i,1); } } if(isb) { fill(flag,flag+num,false); for(int i=0;i<num;i++) { if(!flag[i]) { dfs2(i,-1,0); par[i]=-1; dfs3(i); } } int ret=0; for(int i=0;i<num;i++) {//printf("%d %d %d\n",i+1,ord[i],low[i]); for(int j=0;j<ko[i].size();j++) { if(low[ko[i][j]]>ord[i]) { ret++; } } } printf("%d\n",ret); } else { if(num<=1000&&way<=2000) // if(false) { int ret=0; for(int i=0;i<vec.size();i++) { for(int j=0;j<num;j++) { pat[j].clear(); } for(int j=0;j<vec.size();j++) { if(i!=j) { pat[vec[j].first].push_back(vec[j].second); pat[vec[j].second].push_back(vec[j].first); } } fill(flag,flag+num,false); fill(col,col+num,false); bool iso=true; for(int j=0;j<num;j++) { if(!flag[j]) { iso&=dfs(j,1); } } if(iso) { ret++; } } printf("%d\n",ret); } else { fill(flag,flag+num,false); for(int i=0;i<num;i++) { if(!flag[i]) { dfs2(i,-1,0); par[i]=-1; dfs3(i); } } vector<pii>bbp; vector<pii>abp; vector<pii>gbp; for(int i=0;i<num;i++) { for(int j=0;j<back[i].size();j++) { if(ord[i]>ord[back[i][j]]) { if((depth[i]-depth[back[i][j]]+1)%2==1) { bbp.push_back(make_pair(i,back[i][j])); } else { gbp.push_back(make_pair(i,back[i][j])); } abp.push_back(make_pair(i,back[i][j])); } } } if(bbp.size()==1&&abp.size()==1) { printf("%d\n",depth[bbp[0].first]-depth[bbp[0].second]+1); } else { lcainit(); for(int i=0;i<bbp.size();i++) { imos[bbp[i].first]++; imos[bbp[i].second]++; imos[lca(bbp[i].first,bbp[i].second)]-=2; } for(int i=0;i<gbp.size();i++) { imos[gbp[i].first]--; imos[gbp[i].second]--; imos[lca(gbp[i].first,gbp[i].second)]+=2; } for(int i=0;i<num;i++) { if(par[i]==-1) { dfs4(i); } } int ret=0; if(bbp.size()==1) { ret++; } for(int i=0;i<num;i++) { if(imos[i]==bbp.size()) { ret++; } } printf("%d\n",ret); } } } }
Day4
- Constellation 2 15/100
#include<stdio.h> #include<vector> #include<algorithm> #include<math.h> #include<stdlib.h> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; double eps=1e-10; ll area(pii a,pii b,pii c) { return abs((b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first)); } bool isin(pii a,pii b,pii c,pii p) { return area(a,b,c)==area(a,b,p)+area(b,c,p)+area(c,a,p); } bool iscross(pii a,pii b,pii c,pii d) { if((a.first-b.first)*(c.second-d.second)==(b.second-a.second)*(d.first-c.first)) { return false; } //printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",a.first,a.second,b.first,b.second,c.first,c.second,d.first,d.second); double p=a.first,q=a.second,r=b.first,s=b.second,t=c.first,u=c.second,v=d.first,w=d.second; double y=-double((c.second-d.second)*(a.first*b.second-a.second*b.first)-(b.second-a.second)*(c.second*d.first-c.first*d.second))/double((b.second-a.second)*(d.first-c.first)-(a.first-b.first)*(c.second-d.second)); double x=double((d.first-c.first)*(a.first*b.second-a.second*b.first)-(a.first-b.first)*(c.second*d.first-c.first*d.second))/double((b.second-a.second)*(d.first-c.first)-(a.first-b.first)*(c.second-d.second)); //printf("%lf %lf\n",x,y); if(((x>a.first)!=(x>b.first)||(y>a.second)!=(y>b.second))&&((x>c.first)!=(x>d.first)||(y>c.second)!=(y>d.second))) { //printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",a.first,a.second,b.first,b.second,c.first,c.second,d.first,d.second); //printf("%lf %lf\n",x,y); return true; } return false; } int main() { int num; scanf("%d",&num); vector<pii>v1,v2,v3; ll ret=0; for(int i=0;i<num;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); if(zc==0) { v1.push_back(make_pair(za,zb)); } if(zc==1) { v2.push_back(make_pair(za,zb)); } if(zc==2) { v3.push_back(make_pair(za,zb)); } } for(int i=0;i<v1.size();i++) { for(int j=0;j<v1.size();j++) { for(int k=0;k<v2.size();k++) { for(int l=0;l<v2.size();l++) { for(int m=0;m<v3.size();m++) { for(int n=0;n<v3.size();n++) { pii a=v1[i],b=v2[k],c=v3[m],d=v1[j],e=v2[l],f=v3[n]; if(isin(a,b,c,d)) { continue; } if(isin(a,b,c,e)) { continue; } if(isin(a,b,c,f)) { continue; } if(isin(d,e,f,a)) { continue; } if(isin(d,e,f,b)) { continue; } if(isin(d,e,f,c)) { continue; } if(iscross(a,b,d,e)) { continue; } if(iscross(a,b,e,f)) { continue; } if(iscross(a,b,f,d)) { continue; } if(iscross(b,c,d,e)) { continue; } if(iscross(b,c,e,f)) { continue; } if(iscross(b,c,f,d)) { continue; } if(iscross(c,a,d,e)) { continue; } if(iscross(c,a,e,f)) { continue; } if(iscross(c,a,f,d)) { continue; } ret++; //printf("%d %d %d %d %d %d\n",i,j,k,l,m,n); } } } } } } printf("%lld\n",ret/2); }
Kanji 40/100
#include "Annalib.h" #include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; static ll dist[300][300]; static int tp[6][3]= { {0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1} }; #define INF 4000000000000000000LL; static int SampleFunction() { return 0; } static int SampleVariable; void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { dist[i][j]=INF; } dist[i][i]=0; } for(int i=0;i<M;i++) { dist[A[i]][B[i]]=C[i]; } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { for(int k=0;k<N;k++) { dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]); } } }/* for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { printf("%lld ",dist[i][j]); } printf("\n"); }*/ ll now=0; vector<ll>v; for(int i=0;i<Q;i++) { bool flag=false; for(int j=0;j<K;j++) { if(dist[S[i]][T[i]]==dist[S[i]][A[U[j]]]+C[U[j]]+dist[B[U[j]]][T[i]]) {/* for(int k=0;k<3;k++) { Tap(tp[j+1][k]); }*/ now*=6; now+=j+1; //printf("tap: %d\n",j+1); flag=true; break; } } if(!flag) {/* for(int k=0;k<3;k++) { Tap(tp[0][k]); }*/ now*=6; now+=0; //printf("tap: 0\n"); } if(i%3==2) { v.push_back(now); now=0; } } if(Q%3==1) { v.push_back(now*36); } if(Q%3==2) { v.push_back(now*6); } for(int i=0;i<v.size();i++) { for(int j=7;j>=0;j--) { Tap((v[i]&(1<<j))!=0); } } }
#include "Brunolib.h" #include<stdio.h> #include<vector> #include<algorithm> #include<map> using namespace std; typedef long long ll; typedef pair<int,int>pii; static ll dist[300][300]; static int tp[6][3]= { {0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1} }; static map<pii,int>ma; #define INF 4000000000000000000LL; static ll pat[300][300]; void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { dist[i][j]=INF; } dist[i][i]=0; } for(int i=0;i<M;i++) { ma[make_pair(A[i],B[i])]=i; for(int j=0;j<K;j++) { if(i==U[j]) { goto l01; } } pat[A[i]][B[i]]=C[i]; dist[A[i]][B[i]]=C[i]; l01:; } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { for(int k=0;k<N;k++) { dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]); } } }/* for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { printf("%lld ",dist[i][j]); } printf("\n"); } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { printf("%lld ",pat[i][j]); } printf("\n"); }*/ vector<int>dt; for(int i=0;i<L;i+=8) { int n=0; for(int j=0;j<8;j++) { n*=2; n+=X[i+j]; } dt.push_back(n/36); n%=36; dt.push_back(n/6); dt.push_back(n%6); } for(int i=0;i<Q;i++) { int dat=dt[i]; //printf("%d\n",dat); if(dat==0) { int now=S[i]; for(;;) { if(now==T[i]) { Answer(-1); break; } for(int j=0;j<N;j++) { if(pat[now][j]+dist[j][T[i]]==dist[now][T[i]]&&now!=j&&pat[now][j]>0) { Answer(ma[make_pair(now,j)]); now=j; break; } } } } else { dat--; int now=S[i]; for(;;) { if(now==A[U[dat]]) { break; } for(int j=0;j<N;j++) { if(pat[now][j]+dist[j][A[U[dat]]]==dist[now][A[U[dat]]]&&now!=j&&pat[now][j]>0) { Answer(ma[make_pair(now,j)]); now=j; break; } } } Answer(ma[make_pair(A[U[dat]],B[U[dat]])]); now=B[U[dat]]; for(;;) { if(now==T[i]) { Answer(-1); break; } for(int j=0;j<N;j++) { if(pat[now][j]+dist[j][T[i]]==dist[now][T[i]]&&now!=j&&pat[now][j]>0) { Answer(ma[make_pair(now,j)]); now=j; break; } } } } } }
Straps 100/100
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; #define INF 2100000000 ll dp[2001][6000]; int main() { int num; scanf("%d",&num); vector<pii>vec; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); vec.push_back(make_pair(za,zb)); } for(int i=0;i<=num;i++) { for(int j=0;j<6000;j++) { dp[i][j]=-INF; } } dp[0][3000]=0; ll maxi=0; for(int i=0;i<num;i++) { for(int j=-2000;j<=2000;j++) { //dp[i+1][3000+j]=max(dp[i][3000+j],dp[i][3000+j+1-vec[i].first]+vec[i].second); dp[i+1][3000+min(j-1+vec[i].first,2000LL)]=max(dp[i][3000+j]+vec[i].second,dp[i+1][3000+min(j-1+vec[i].first,2000LL)]); dp[i+1][3000+j]=max(dp[i+1][3000+j],dp[i][3000+j]);/* if(j>=-1) { maxi=max(maxi,dp[i+1][3000+j]); }*/ } } for(int i=0;i<=num;i++) { for(int j=-1;j<=2000;j++) { maxi=max(maxi,dp[i][j+3000]); } } printf("%lld\n",maxi); }
340+300+215+155=1010
