beet's soil

競プロのことなど

Codeforces Round #398 (Div. 2)

初太陽記念カキコ

【A. Snacktower】

よくわからなかった(完)。

【B. The Queue】

問題文に書いてある通りに実装したらWAだった。
(other than the one he already serves).とはなんだったのか。
エスパーコンやめちくり〜。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll ts,tf,t,n;
  cin>>ts>>tf>>t>>n;
  ll a[n];
  for(ll i=0;i<n;i++) cin>>a[i];
  set<ll> s;
  for(ll i=0;i<n;i++) s.insert(a[i]);

  
  if(!n||ts<a[0]){
    cout<<ts<<endl;
    return 0;
  }
  
  ll ans=a[0]-1,len=ts-a[0]+1;
  queue<int> q;
  ll i=0,c=ts;
  while(c<tf&&i<n){
    while(i<n&&a[i]<=c){
      if(i==0||a[i-1]!=a[i]){
	if(!s.count(a[i]-1)){
	  if((int)q.size()*t+c+t<=tf){
	    if((int)q.size()*t+c-(a[i]-1)<len){
	      len=q.size()*t+c-(a[i]-1);
	      ans=a[i]-1;
	    }
	  }
	}
      }
      
      q.push(i);
      if(i+1>=n||a[i]!=a[i+1]){
	if((int)q.size()*t+c+t<=tf){
	  if((int)q.size()*t+c-a[i]<len){
	    len=q.size()*t+c-a[i];
	    ans=a[i];
	  }
	}
      }
      
      i++;
    }
    if(q.empty()&&c+t<=tf){
      cout<<c<<endl;
      return 0;
    }
    while(!q.empty()){
      q.pop();
      c+=t;
    }
  }
  if(i==n&&c+t<=tf){
    cout<<c<<endl;
    return 0;
  }
  /*
  if(len==ts-a[0]+1){
    time_t start=clock();
    while((double)(clock()-start)/CLOCKS_PER_SEC<1.0);
  }
  */
  //cout<<len<<endl;
  cout<<ans<<endl;
  return 0;
}
【C. Garland】

2回dfsして1回目で部分木の重みの和、2回目で判定する。
根元も切れるようになっててWA(ア。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX_V 1000050
vector<int> G[MAX_V];
int root=0,sum;
int t[MAX_V];
int s[MAX_V];
int dfs(int v,int p=-1){
  int res=t[v];
  for(int u:G[v]) if(u!=p) res+=dfs(u,v);
  //cout<<v<<" "<<res<<endl;
  return s[v]=res;
}
int dfs2(int v,int p=-1){
  int an[2],i=0;
  for(int u:G[v]){
    if(u!=p){
      int k=dfs2(u,v);
      if(~k) an[i++]=k;
      if(i>1) break;
    }
  }
  if(i>1){
    cout<<an[0]+1<<" "<<an[1]+1<<endl;
    assert(s[an[0]]*3==sum);
    assert(s[an[1]]*3==sum);
    exit(0);
  }
  if(i&&v!=root){
    if(s[v]*3==sum*2){
      an[1]=v;
      cout<<an[0]+1<<" "<<an[1]+1<<endl;
      assert(s[an[0]]*3==sum);
      assert(s[an[1]]*3==sum*2);
      exit(0);
    }
    return an[0];
  }
  bool f=s[v]*3==sum;
  //cout<<v<<" "<<i<<" "<<(f?v:-1)<<endl;
  return f?v:-1;
}
signed main(){
  int n;
  scanf("%lld",&n);
  for(int i=0;i<n;i++){
    int a;
    scanf("%lld %lld",&a,t+i);
    a--;
    if(~a){
      G[i].push_back(a);
      G[a].push_back(i);
    }else root=i;
  }
  dfs(root);
  sum=s[root];
  dfs2(root);
  //time_t start=clock();
  //while((double)(clock()-start)/CLOCKS_PER_SEC<1.0);
  cout<<-1<<endl;
  return 0;
}
【全体】

xxx-- 0points 2246th 
1707 -> 1574 (-133)

たのしいね☀️☀️☀️☀️☀️(白目)。