oj.uz

Submission #932368

# Submission time Handle Problem Language Result Execution time Memory
932368 2024-02-23T08:54:31 Z kxd Shortcut (IOI16_shortcut) C++17
0 / 100
 19 ms 6492 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 int 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

Compilation message

shortcut.cpp:34:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   34 |     const int INF = 1e18;
      |                     ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB n = 4, 80 is a correct answer
2 Correct 19 ms 6492 KB n = 9, 110 is a correct answer
3 Correct 4 ms 6488 KB n = 4, 21 is a correct answer
4 Correct 3 ms 6488 KB n = 3, 4 is a correct answer
5 Correct 2 ms 6492 KB n = 2, 62 is a correct answer
6 Correct 3 ms 6492 KB n = 2, 3 is a correct answer
7 Correct 3 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 6492 KB n = 2, 3 is a correct answer
10 Correct 2 ms 6492 KB n = 2, 2000000001 is a correct answer
11 Incorrect 2 ms 6492 KB n = 2, incorrect answer: jury 3000000000 vs contestant 2147483647
12 Halted 0 ms 0 KB -