Submission #1032255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032255		Antekb	Board Game (JOI24_boardgame)	C++17	68 / 100	4006 ms	18968 KiB

Main

#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";
	}
}

Compilation message (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++){
      |               ~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 9 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9