Submission #1206737

#TimeUsernameProblemLanguageResultExecution timeMemory
1206737mychecksedadBoard Game (JOI24_boardgame)C++20
17 / 100
3113 ms29900 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, m, k, a[N], is[N]; vi g[N]; ll DP[N]; array<ll, 3> res[N][2]; // 2 dif results for players for 2...k void solve(){ cin >> n >> m >> k; for(int i = 1; i <= m; ++i){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } string s; cin >> s; for(int i = 1; i <= n; ++i){ if(s[i-1] == '0') is[i] = 1; else is[i] = 0; } for(int i = 1; i <= k; ++i){ cin >> a[i]; } vector<int> dist(n + 1, N); vector<pii> dist2(n + 1, pii{N, N}); queue<int> q; priority_queue<array<int, 3>> qq; for(int i = 1; i <= n; ++i){ if(is[i] == 0){ dist[i] = 0; q.push(i); } } while(!q.empty()){ int v = q.front(); q.pop(); for(int u: g[v]){ if(dist[u] == N){ dist[u] = dist[v] + 1; q.push(u); } } } for(int i = 1; i <= n; ++i){ if(is[i] == 0){ for(int u: g[i]){ if(is[u] == 0){ dist2[i] = {0, 0}; qq.push({0, 0, i}); break; } } } } vector<bool> VIS(n + 1); while(!qq.empty()){ int v = qq.top()[2]; qq.pop(); if(VIS[v]) continue; VIS[v] = 1; for(int u: g[v]){ int new_dist = dist2[v].ff + (is[v] == 0 ? 0 : 1); if(dist2[u].ff > new_dist){ dist2[u] = {new_dist, dist2[v].ss}; if(is[v] == 0){ dist2[u].ss++; } qq.push({-dist2[u].ff, -(int)(is[u]), u}); } } } for(int i = 0; i <= n; ++i){ DP[i] = 0; } // for(int i = 1; i <= n; ++i){ // cerr << dist2[i].ff << ' ' << dist2[i].ss << '\n'; // } for(int i = 2; i <= k; ++i){ // first one res[i][0] = {1, dist[a[i]], 2}; // at first, dist[a[i]], then just +2 +2 +2 +2... res[i][1] = {dist2[a[i]].ss, dist2[a[i]].ff + dist2[a[i]].ss, 1}; // we will wait for dist2[a[i]].ss phases to take it, then +1 +1 +1 +1... for(ll j = 1; j <= n; ++j){ // i-th player's contribution to j-th phase, I guess ll best = MOD; if(res[i][1][0] == 0){ // if it's already a type-2 cell best = min(best, j); }else{ if(res[i][1][0] <= j){ // we need to pass phases best = min(best, res[i][1][1] + (j - res[i][1][0])); } } if(res[i][0][1] == 0){ // we begin at a stop cell, type-1 cell best = min(best, j * 2); }else{ best = min(best, res[i][0][1] + 2 * (j - 1)); // rest } DP[j] += best; // cerr << i << ' ' << j << ' ' << best << '\n'; } } priority_queue<array<ll, 3>> Q; // -dist, phase, node Q.push({0, 0, a[1]}); vector<bool> vis(n + 1); vector<ll> DIST(n + 1, (ll)(1e18)); DIST[a[1]] = 0; while(!Q.empty()){ int v = Q.top()[2], phase = Q.top()[1]; Q.pop(); // cerr << v << ' ' << phase << '\n'; if(vis[v]) continue; vis[v] = 1; for(int u: g[v]){ ll w = (is[v] == 0 && v != a[1] ? DP[phase + 1] - DP[phase] : 0ll) + 1; if(!vis[u] && DIST[u] > DIST[v] + w){ DIST[u] = DIST[v] + w; Q.push({-DIST[u], (is[v] == 0 && v != a[1] ? phase + 1 : phase), u}); } } } // for(int i = 1; i <= n; ++i){ // cerr << i << ": " << DP[i] << '\n'; // } // en; for(int i = 1; i <= n; ++i){ cout << DIST[i] << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#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...