beet's soil

競プロのことなど

AtCoder Beginner Contest 061

134th Dで12WAはダメ

【A - Between Two Integers】

問題文を読む(完)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout<<(a<=c&&c<=b?"Yes":"No")<<endl;
  return 0;
}
【B - Counting Roads】

問題文を読む2(完)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int ans[55]={};
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    ans[a]++;ans[b]++;
  }
  for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
  return 0;
}
【C - Big Array】

愚直にやると10^18になってアなのでまあはいする。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
signed main(){
  int n,k;
  cin>>n>>k;
  P p[n];
  for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
  sort(p,p+n);
  for(int i=0;i<n;i++){
    if(k>p[i].second) k-=p[i].second;
    else{
      cout<<p[i].first<<endl;
      return 0;
    }
  }
  return 0;
}
【D - Score Attack】

なにげにベルマンフォードを初めて書いた。
ゴールに到達できない負閉路を考慮していなくてINFWA生えて泣いた。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX_V 2050
#define INF (1LL<<60LL)
typedef pair<int,int> P;
int V;
struct edge2{
  int from,to,cost;
  edge2(){}
  edge2(int from,int to,int cost):from(from),to(to),cost(cost){}
};
edge2 es[2050];
int d[2050];
int ok[1111];
int used[1111];
int shortest_path(int s,int e){
  for(int i=0;i<V;i++) d[i]=INF;
  d[s]=0;
  for(int j=0;j<V;j++){
    bool update=0;
    for(int i=0;i<e;i++){
      edge2 e=es[i];
      if(!ok[e.from]||!ok[e.to]) continue;
      if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
	d[e.to]=d[e.from]+e.cost;
	update=1;
      }
    }
    if(!update) break;
    if(j==V-1){
      cout<<"inf"<<endl;
      exit(0);
    } 
  }
  return d[V-1];
}

vector<int> G[1111];
void dfs2(int v){
  if(used[v]) return;
  used[v]=1;
  for(int u:G[v]){
    dfs2(u);
  }
}

signed main(){
  int v,e;
  cin>>v>>e;
  for(int i=0;i<e;i++){
    int u,v,d;
    cin>>u>>v>>d;u--;v--;
    G[u].push_back(v);
    es[i]=edge2(u,v,-d);
  }
  for(int i=0;i<v;i++){
    memset(used,0,sizeof(used));
    dfs2(i);
    ok[i]=used[v-1];
  }
  V=v;
  cout<<-shortest_path(0,e)<<endl;
  return 0;
}

ABCは2桁順位取りたいなあ…