Submission #932372

#TimeUsernameProblemLanguageResultExecution timeMemory
932372kxdShortcut (IOI16_shortcut)C++17
0 / 100
27 ms6696 KiB
        #define tj
        #ifdef tj
        #include "shortcut.h"
        #endif
        #include <bits/stdc++.h>
        //#define DEBUG 1106
        //#define int long long
        #define ll long long
        #define ld long double
        #define pb push_back
        #define p_q priority_queue
        #define m_p make_pair
        #define pii pair<ll,ll>
        #define endl '\n'
        #define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #define FOR(i,a,b) for(int i = a; i <= b; i++)
        #define forn(i,n) for (int i = 0; i < n; i++)
        #define forn1(i,n) for (int i = 1; i <= n; i++)
        #define all(x) x.begin(),x.end()
        #define ft first
        #define sd second
        #define lowbit(x) (x&(-x))
        #define chmax(x,y) x=max(x,y)
        #define chmin(x,y) x=min(x,y)
        #ifdef DEBUG
        #define debug(x) cout << #x << ": " << x << endl;
        #else
        #define debug(x) 1106;
        #endif
         
        using namespace std;
        const int N = 2e5+5;
        const int inf = 1e9;
        const ll INF = 1e18;
        const int MOD = 1e9+7;
         
        int n;
        vector<pii> G[N];
        ll dis[N];
         
        long long src(int x) {
        	p_q<pii, vector<pii>, greater<pii>> pq;
        	pq.push(m_p(0, x));
        	dis[x] = 0;
        	ll ans = 0;
        	while (!pq.empty()) {
        		pii c = pq.top();
        		pq.pop();
        		if (dis[c.sd] != c.ft) continue;
        		for (auto i : G[c.sd]) {
        			if (dis[i.ft] == -1 || dis[i.ft] > i.sd+c.ft) {
        				dis[i.ft] = i.sd+c.ft;
        				chmax(ans,dis[i.ft]);
        				pq.push(m_p(dis[i.ft], i.ft));
        			}
        		}
        	}
        	return ans;
        }
         
        long long find_diameter() {
        	ll ans = 0;
        	forn(i,n*2+2) {
        		//if(!G[i].size()) continue;
        		memset(dis,-1,sizeof(dis));
        		chmax(ans,src(i));
        	}
        	return ans;
        }
         
        long long find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
            n = n_;
            forn(i,n) {
            	if(i!=n-1) {
            		G[i].pb({i+1,l[i]});
            		G[i+1].pb({i,l[i]});
        		}
            	if(d[i]) {
            		G[i].pb({i+n,d[i]});
            		G[i+n].pb({i,d[i]});
        		}
        	}
        	ll ans = INF;
        	for(int i = 0; i < n-1; i++) {
        		for(int j = i+1; j <= n-1; j++) {
        			G[i].pb({j,c});
        			G[j].pb({i,c});
        			ll t = find_diameter();
        			chmin(ans,t);
        			G[i].pop_back();
        			G[j].pop_back();
        		}
        	}
        	return ans;
        }
        #ifndef tj
        int main() {
            int n, c;
            assert(2 == scanf("%d%d", &n, &c));
            
            std::vector<int> l(n - 1);
            std::vector<int> d(n);
            for (int i = 0; i < n - 1; i++)
                assert(1 == scanf("%d", &l[i]));
            for (int i = 0; i < n; i++)
                assert(1 == scanf("%d", &d[i]));
            long long t = find_shortcut(n, l, d, c);
            printf("%lld\n", t);
            
            return 0;
        }
        #endif
#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...