遅いのとA,B逆なことを除けばうまくいった?
A |
B |
C |
D |
E |
Place |
00:26 |
00:33 |
01:28 |
- |
- |
20th |
A:
全然わかりませんでした(オイ
バス乗車時間を二分探索。式もなんだか難しい。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int main(){
int a,b,c,d,e;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
double left=0;
double right=(double)b/d;
int r=(a+e-1)/e;
for(int i=0;i<100;i++){
double M=(left+right)/2;
double at=0;
double t=0;
double x=0;
for(int j=0;j<r;j++){
t+=M;
at+=M*d;
if(j==r-1)break;
x=t*c;
double t2=(at-x)/(c+d);
x+=t2*c;
at=x;
t+=t2;
}
if(at<b){
left=M;
}else right=M;
}
printf("%.12f\n",left+((double)b-left*d)/c);
}
B:
辺ごとに両端の少ない方だけ人が移動する。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int v[210000];
vector<int>g[221000];
long long ret=0;
int sz[221000];
int M;
void dfs(int a,int b){
for(int i=0;i<g[a].size();i++){
if(b==g[a][i])continue;
dfs(g[a][i],a);
sz[a]+=sz[g[a][i]];
ret+=min(sz[g[a][i]],M-sz[g[a][i]]);
}
if(v[a])sz[a]++;
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
M=b*2;
for(int i=0;i<b*2;i++){
int p;scanf("%d",&p);p--;v[p]++;
}
for(int i=0;i<a-1;i++){
int p,q;scanf("%d%d",&p,&q);p--;q--;
g[p].push_back(q);
g[q].push_back(p);
}
dfs(0,-1);
printf("%I64d\n",ret);
}
C:
まずDinic (計算量的にも問題なし)。流量0のときと3以上のときは自明。
流量が1,2いずれのときも1つの辺はフローで流れた辺を使う。2のときは残った辺もフローで流れた辺。
フローで使った辺を1つ選び、残りでs->tの移動中必ず通る辺(dfs情報のアレでチェック可能)を全部試せばよい。1のときはフローで使った辺を消したあとBFSしてs->tいけるかどうかも判断する。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const int D_MAX_V=1002;
const int D_v_size=1002;
struct D_wolf{
int t,c,r;
int u,w;
D_wolf(){t=c=r=u=w=0;}
D_wolf(int t1,int c1,int r1,int u1,int w1){
t=t1;c=c1;r=r1;u=u1;w=w1;
}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];
void add_edge(int from,int to,int cap,int id){
D_G[from].push_back(D_wolf(to,cap,D_G[to].size(),1,id));
D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1,0,id));
}
void D_bfs(int s){
for(int i=0;i<D_v_size;i++)D_level[i]=-1;
queue<int> Q;
D_level[s]=0;
Q.push(s);
while(Q.size()){
int v=Q.front();
Q.pop();
for(int i=0;i<D_G[v].size();i++){
if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
D_level[D_G[v][i].t]=D_level[v]+1;
Q.push(D_G[v][i].t);
}
}
}
}
int D_dfs(int v,int t,int f){
if(v==t)return f;
for(;D_iter[v]<D_G[v].size();D_iter[v]++){
int i=D_iter[v];
if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
if(d>0){
D_G[v][i].c-=d;
D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow=0;
for(;;){
D_bfs(s);
if(D_level[t]<0)return flow;
for(int i=0;i<D_v_size;i++)D_iter[i]=0;
int f;
while((f=D_dfs(s,t,99999999))>0){flow+=f;}
}
return 0;
}
const int MAXN=1100;
const int MAXM=61000;
int zeit, dis[MAXN], fin[MAXN], low[MAXN], par[MAXN], dep[MAXN];
int kodat[MAXN], koptr[MAXN + 1];
int zu[MAXM];
int ptr[MAXN];
int nxt[MAXM];
int n;
void dfsInfo(int u, int oy, int d) {
dis[u] = low[u] = zeit++; par[u] = oy; dep[u] = d;
int i, v;
for (i = ptr[u]; ~i; i = nxt[i]) if ((v = zu[i]) != oy) {
if (!~dis[v]) {
dfsInfo(v, u, d + 1);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dis[v]);
}
}
fin[u] = zeit++;
}
void dfsInfos() {
memset(dis, ~0, n * 4); zeit = 0;
for (int u = 0; u < n; ++u) if (!~dis[u]) dfsInfo(u, -1, 0);
for (int u = 0; u < n; ++u) {
int &j = koptr[u + 1] = koptr[u];
for (int i = ptr[u]; ~i; i = nxt[i]) if (u == par[zu[i]]) kodat[j++] = zu[i];
}
}
bool produce(int u, int v) {
return (dis[u] <= dis[v] && fin[u] >= fin[v]);
}
int related(int u, int v) {
int s = koptr[u], e = koptr[u + 1], h;
for (; s + 1 < e; ) {
h = (s + e) >> 1;
(dis[kodat[h]] <= dis[v]) ? s = h : e = h;
}
return kodat[s];
}
bool isBridge(int u, int v) {
if (dis[u] > dis[v]) swap(u, v);
return (u == par[v] && dis[v] <= low[v]);
}
bool isFatalEdge(int u, int v, int a, int b) {
if (dis[u] > dis[v]) swap(u, v);
return (u == par[v] && dis[v] <= low[v] && produce(v, a) != produce(v, b));
}
bool isFatalPoint(int u, int a, int b) {
bool ua = produce(u, a), ub = produce(u, b);
if (!ua && !ub) {
return 0;
} else if (ua && ub) {
int ra = related(u, a), rb = related(u, b);
return (ra != rb && (dis[u] <= low[ra] || dis[u] <= low[rb]));
} else {
if (ub) swap(a, b);
return (dis[u] <= low[related(u, a)]);
}
}
int vis[1100];
int x[31000];
int y[31000];
int z[31000];
int f[1100][1100];
vector<pair<int,int> > G[1100];
int main(){
int a,b;
scanf("%d%d",&a,&b);
int s,t;scanf("%d%d",&s,&t);
s--;t--;
for(int i=0;i<b;i++){
int p,q,r;scanf("%d%d%d",&p,&q,&r);p--;q--;
f[p][q]++;
f[q][p]++;
x[i]=p;y[i]=q;z[i]=r;
if(p==q)continue;
add_edge(p,q,1,i);
add_edge(q,p,1,i);
}
int ans=max_flow(s,t);
if(ans>2){
printf("-1\n");return 0;
}
if(ans==0){
printf("0\n0\n");return 0;
}
for(int i=0;i<a;i++){
for(int j=0;j<D_G[i].size();j++){
if(D_G[i][j].u&&D_G[i][j].c==0){
G[i].push_back(make_pair(D_G[i][j].t,D_G[i][j].w));
}
}
}
int ret=mod*2;
int L=-1;
int R=-1;
for(int i=0;i<a;i++)for(int j=0;j<G[i].size();j++){
for(int k=0;k<b;k++){
zu[k]=nxt[k]=-1;
}
for(int k=0;k<=a;k++){
dis[k]=fin[k]=low[k]=par[k]=dep[k]=kodat[k]=koptr[k]=0;
ptr[k]=-1;
}
int cur=z[G[i][j].second];
zeit=0;
int sz=0;
for(int k=0;k<b;k++){
if(x[k]==y[k])continue;
if(G[i][j].second==k)continue;
zu[sz]=y[k];
nxt[sz]=ptr[x[k]];
ptr[x[k]]=sz++;
zu[sz]=x[k];
nxt[sz]=ptr[y[k]];
ptr[y[k]]=sz++;
}
n=a;
if(ans==1&&ret>cur){
for(int k=0;k<a;k++)vis[k]=0;
queue<int>Q;
Q.push(s);
vis[s]=1;
while(Q.size()){
int at=Q.front();Q.pop();
for(int k=ptr[at];~k;k=nxt[k]){
if(!vis[zu[k]]){
vis[zu[k]]=1;
Q.push(zu[k]);
}
}
}
if(vis[t]==0){
ret=cur;
L=G[i][j].second;
R=-1;
}
}
dfsInfos();
for(int k=0;k<b;k++){
if(x[k]==y[k])continue;
if(G[i][j].second==k)continue;
if(ret>cur+z[k]&&isFatalEdge(x[k],y[k],s,t)&&(f[x[k]][y[k]]==1||(f[x[k]][y[k]]==2&&((i==x[k]&&G[i][j].first==y[k])||(i==y[k]&&G[i][j].first==x[k]))))){
ret=cur+z[k];
L=G[i][j].second;
R=k;
}
}
}
if(~R){
printf("%d\n2\n%d %d\n",ret,L+1,R+1);
}else printf("%d\n1\n%d\n",ret,L+1);
}
D:
人間が解ける問題には見えない。Mo+ハフマン木の回転、とかではないなら結構面白いのかも。