제출 #1032255

#제출 시각아이디문제언어결과실행 시간메모리
1032255AntekbBoard Game (JOI24_boardgame)C++17
68 / 100
4006 ms18968 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("trapv") #define st first #define nd second #define pb push_back #define pp pop_back #define eb emplace_back #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.st<<", "<<m.nd<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #ifdef LOCAL #define deb(x...) cerr<<#x<<" = ";debug(x); #else #define deb(...) #endif ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=2e5+5, INF=1e9+5, mod=1e9+7; int typ[N], zera[N], bliska[N], dist2[N]; int licz[N]; ll tab[N], pref[N], pref2[N], dist[N]; vi E[N], co[N]; void solve(int n, int s, ll cost, bool b){ //cost--; dist[s]=0; licz[s]=0; priority_queue<pair<ll, int> > Q; if(b==1)Q.push({0, s}); else{ for(int i=1; i<=n; i++) dist[i]+=cost*licz[i], Q.push({-dist[i], i}); } while(Q.size()){ int v=Q.top().nd; ll d=-Q.top().st; Q.pop(); if(d!=dist[v])continue; for(int u:E[v]){ if(dist[u]>dist[v]+1+typ[u]*cost){ dist[u]=dist[v]+1+typ[u]*cost; licz[u]=licz[v]+typ[u]; Q.push({-dist[u], u}); } } } } int main(){ BOOST; int n, m, k; cin>>n>>m>>k; //assert(n<=3000); for(int i=0; i<m; i++){ int u, v;cin>>u>>v; E[u].pb(v); E[v].pb(u); } string s; cin>>s; for(int i=0; i<n; i++)typ[i+1]=s[i]-'0'; for(int i=1; i<=n; i++){ zera[i]=1e9; for(int u:E[i]){ if(typ[u] && typ[i])zera[i]=0; } } vi V; for(int i=1; i<=n; i++){ if(zera[i]==0)V.pb(i); } for(int i=0; i<V.size(); i++){ int v=V[i]; for(int u:E[v]){ if(zera[u]>zera[v]+1-typ[u]){ zera[u]=zera[v]+1-typ[u]; V.pb(u); } } } V.clear(); for(int i=1; i<=n; i++){ if(typ[i]==0)bliska[i]=1e9; else V.pb(i); } for(int i=0; i<V.size(); i++){ int v=V[i]; for(int u:E[v]){ if(bliska[u]==1e9){ bliska[u]=bliska[v]+1; V.pb(u); } } } for(int i=1; i<=n; i++){ deb(i, bliska[i], zera[i]); } vi X(k); for(int &i:X)cin>>i; deb(X); for(int i=1; i<k; i++){ if(typ[X[i]]==1){ /*for(int j=1; j<n; j++){ tab[j]+=min(2*j, j+zera[X[i]]); }*/ pref2[1]+=2; if(zera[X[i]]!=1e9)pref2[zera[X[i]]+1]--; } else{ ll t=min(-1+bliska[X[i]], zera[X[i]]-1); /*for(int j=1; j<n; j++){ //deb(j, 2*j-2+bliska[X[i]], j+zera[X[i]]); tab[j]+=min(j-2+bliska[X[i]], zera[X[i]]-1)-t; }*/ pref2[1]+=1; pref[1]+=t; if(zera[X[i]]-1 >t){ pref2[2]++; if(zera[X[i]]!=1e9){ pref2[1+zera[X[i]]-t]--; } } } } for(int i=0; i<n; i++){ pref2[i+1]+=pref2[i]; } for(int i=0; i<n; i++){ pref[i+1]+=pref[i]+pref2[i+1]; } for(int i=0; i<n; i++){ tab[i]+=pref[i]; } vector<ll> ans(n+1, 1e18); ans[X[0]]=0; for(int i=1; i<=n; i++)dist[i]=1e9; dist[X[0]]=0; vector<int> changed={X[0]}; for(int ile=0; ile<2; ile++){//ile skokow vi wazne; for(int i:changed){ if(dist[i]!=1e9){ co[dist[i]].pb(i); wazne.pb(dist[i]); } } sort(all(wazne)); changed.clear(); vii todo; for(int d:wazne){ while(co[d].size()){ for(int v:co[d]){ for(int u:E[v]){ if(typ[u]==0 && dist[u]>dist[v]+1){ changed.pb(u); dist[u]=dist[v]+1; co[dist[u]].pb(u); } if(typ[u]==1 && dist[v]<dist[u]){ todo.pb({dist[v], u}); //dist[u]=dist[v]; changed.pb(u); } } } co[d].clear(); d++; } } sort(all(todo)); reverse(all(todo)); for(pii i:todo){ dist[i.nd]=i.st; } for(int i:changed){ if(dist[i]==1e9)continue; if(i==1){ deb(ile, i, dist[i], tab[ile], typ[i],dist[i]+tab[ile]+typ[i]+ile); } if(ile<2) ans[i]=min(ans[i], dist[i]+tab[ile]+typ[i]+ile); } } for(int i=1; i<=n; i++){ dist[i]=1e9; dist2[i]=1e9; } for(int i=1; i<=n; i++)dist[i]=1e18; for(int i=1; i<n; i++){ deb(tab[i]); if(i>1 && (i==2 || tab[i]-tab[i-1]!=tab[i-1]-tab[i-2])){ solve(n, X[0], tab[i]-tab[i-1], i==2); ll cost=tab[i]-i*(tab[i]-tab[i-1]); deb(i, dist[1], cost, tab[i]-tab[i-1]); for(int j=1; j<=n; j++){ if(licz[j]-typ[j]>=i-1) ans[j]=min(ans[j], dist[j]+cost-typ[j]*(tab[i]-tab[i-1])); dist[j]-=licz[j]*(tab[i]-tab[i-1]); } } } ans[X[0]]=0; for(int i=1; i<=n; i++){ cout<<ans[i]<<"\n"; } }

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

Main.cpp: In function 'int main()':
Main.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
Main.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...