제출 #607158

#제출 시각아이디문제언어결과실행 시간메모리
607158Koosha_mvRoller Coaster Railroad (IOI16_railroad)C++14
64 / 100
424 ms104368 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=1e6+99,inf=1e9+99; int n,m,cnt,in[N],out[N],vis[N]; ll dp[(1<<18)][18]; vector<int> ga[N],gb[N]; void reset(){ cnt=0; f(i,0,n) vis[i]=0; } void add(int u,int v,int t){ //cout<<u<<" "<<v<<" -> "<<t<<endl; in[v]+=t; out[u]+=t; ga[u].pb(v); gb[v].pb(u); } void dfs(int u,vector<int> *g){ cnt++; vis[u]=1; for(auto v : g[u]){ if(vis[v]==1) continue ; dfs(v,g); } } ll plan_roller_coaster(vector<int> s,vector<int> t) { m=s.size(); if(s.size()<17){ m++; s.pb(0); t.pb(0); f(mask,0,(1<<m)) f(i,0,m) dp[mask][i]=1ll*inf*N; dp[(1<<(m-1))][m-1]=0; f(mask,1,(1<<m)){ f(i,0,m){ if(bit(mask,i)==0) continue ; f(j,0,m){ if(bit(mask,j)==1) continue ; minm(dp[mask^(1<<j)][j],dp[mask][i]+max(0ll,1ll*t[i]-s[j])); } } } ll ans=1ll*inf*N; f(i,0,m) minm(ans,dp[(1<<m)-1][i]); return ans; } vector<int> vec; vec.pb(0); vec.pb(inf); f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]); sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); n=vec.size(); f(i,0,s.size()){ int u=lower_bound(all(vec),s[i])-vec.begin(),v=lower_bound(all(vec),t[i])-vec.begin(); add(u,v,1); } add(n-1,0,1); f(i,0,n-1){ if(in[i]<out[i]) return 1; if(in[i]>out[i]){ add(i,i+1,in[i]-out[i]); } } f(i,0,n){ //cout<<in[i]<<" - "<<out[i]<<endl; } reset(); dfs(0,ga); if(cnt<n) return 1; reset(); dfs(0,gb); if(cnt<n) return 1; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   74 |     f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
      |       ~~~~~~~~~~~~             
railroad.cpp:74:5: note: in expansion of macro 'f'
   74 |     f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
      |     ^
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   78 |     f(i,0,s.size()){
      |       ~~~~~~~~~~~~             
railroad.cpp:78:5: note: in expansion of macro 'f'
   78 |     f(i,0,s.size()){
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...