oj.uz

Submission #932372

# Submission time Handle Problem Language Result Execution time Memory
932372 2024-02-23T08:57:03 Z kxd Shortcut (IOI16_shortcut) C++17
0 / 100
 27 ms 6696 KB 
        #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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 20 ms 6692 KB n = 9, 110 is a correct answer
3 Correct 3 ms 6492 KB n = 4, 21 is a correct answer
4 Correct 2 ms 6492 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 2 ms 6492 KB n = 3, 29 is a correct answer
8 Correct 2 ms 6492 KB n = 2, 3 is a correct answer
9 Correct 2 ms 6488 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 6488 KB n = 2, 3000000000 is a correct answer
12 Correct 3 ms 6492 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 6492 KB n = 3, 3000000000 is a correct answer
14 Correct 4 ms 6488 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 6492 KB n = 4, 4000000000 is a correct answer
16 Correct 5 ms 6528 KB n = 5, 4000000000 is a correct answer
17 Correct 26 ms 6492 KB n = 10, 1000000343 is a correct answer
18 Correct 27 ms 6488 KB n = 10, 3189 is a correct answer
19 Correct 25 ms 6492 KB n = 10, 7000000000 is a correct answer
20 Correct 5 ms 6492 KB n = 5, 12 is a correct answer
21 Correct 5 ms 6492 KB n = 5, 25 is a correct answer
22 Correct 2 ms 6696 KB n = 2, 122 is a correct answer
23 Correct 26 ms 6492 KB n = 10, 117 is a correct answer
24 Correct 26 ms 6492 KB n = 10, 336 is a correct answer
25 Incorrect 27 ms 6676 KB n = 10, incorrect answer: jury 438 vs contestant 455
26 Halted 0 ms 0 KB -