oj.uz

Submission #1106735

# Submission time Handle Problem Language Result Execution time Memory
1106735 2024-10-31T02:14:06 Z ro9669 Voting Cities (NOI22_votingcity) C++17
45 / 100
 1000 ms 6632 KB 
 #include <bits/stdc++.h>
 #define fi first
 #define se second
 #define all(v) v.begin() , v.end()
 #define sz(v) int(v.size())
 #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
 using namespace std;

 typedef long long ll;
 typedef pair<int , int> ii;
 typedef pair<long long , int> lli;

 const int maxN = int(5e3)+7;
 const ll inf = ll(1e18)+7;

 int n , m , k , q , en[maxN] , c[5];
 ll dp[maxN][1<<5];
 vector<ii> g[maxN];

 void solve(){
    cin >> n >> m >> k;
    for (int i = 0 ; i < k ; i++){
        cin >> en[i];
    }
    for (int i = 0 ; i < m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v , w});
    }
    cin >> q;
    while (q--){
        int st; cin >> st;
        for (int i = 0 ; i < 5 ; i++) cin >> c[i];
        for (int i = 0 ; i < n ; i++){
            for (int mask = 0 ; mask < (1<<5) ; mask++) dp[i][mask] = inf;
        }
        dp[st][0] = 0;
        priority_queue<pair<ll , ii> , vector<pair<ll , ii>> , greater<pair<ll , ii>>> pq;
        pq.push({dp[st][0] , {st , 0}});
        while (pq.empty() == false){
            auto it = pq.top(); pq.pop();
            int u = it.se.fi;
            int mask = it.se.se;
            if (dp[u][mask] != it.fi) continue;
            for (auto e : g[u]){
                int v = e.fi;
                int w = e.se;
                if (dp[v][mask] > dp[u][mask] + 1ll * w){
                    dp[v][mask] = dp[u][mask] + 1ll * w;
                    pq.push({dp[v][mask] , {v , mask}});
                }
                for (int i = 0 ; i < 5 ; i++){
                    if ((mask>>i)&1) continue;
                    if (c[i] == -1) continue;
                    if (dp[v][mask ^ (1<<i)] > dp[u][mask] + 1ll * c[i] + (1ll * (10 - i - 1) * w) / 10){
                        dp[v][mask ^ (1<<i)] = dp[u][mask] + 1ll * c[i] + (1ll * (10 - i - 1) * w) / 10;
                        pq.push({dp[v][mask ^ (1<<i)] , {v , (mask ^ (1<<i))}});
                    }
                }
            }
        }
        ll ans = inf;
        for (int i = 0 ; i < k ; i++){
            for (int mask = 0 ; mask < (1<<5) ; mask++){
                ans = min(ans , dp[en[i]][mask]);
            }
        }
        if (ans == inf) ans = -1;
        cout << ans << "\n";
    }
 }

 #define name "A"

 int main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     if (fopen(name".INP" , "r")){
         freopen(name".INP" , "r" , stdin);
         freopen(name".OUT" , "w" , stdout);
     }
     int t = 1; //cin >> t;
     while (t--) solve();
     return 0;
 }

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |          freopen(name".INP" , "r" , stdin);
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |          freopen(name".OUT" , "w" , stdout);
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 46 ms 2128 KB Output is correct
7 Correct 22 ms 1872 KB Output is correct
8 Correct 64 ms 2128 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 432 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 46 ms 2128 KB Output is correct
7 Correct 22 ms 1872 KB Output is correct
8 Correct 64 ms 2128 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 56 ms 2128 KB Output is correct
12 Correct 22 ms 1872 KB Output is correct
13 Correct 63 ms 2128 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 336 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 49 ms 5316 KB Output is correct
7 Correct 7 ms 1872 KB Output is correct
8 Correct 15 ms 2764 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 46 ms 2128 KB Output is correct
7 Correct 22 ms 1872 KB Output is correct
8 Correct 64 ms 2128 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 49 ms 5316 KB Output is correct
12 Correct 7 ms 1872 KB Output is correct
13 Correct 15 ms 2764 KB Output is correct
14 Execution timed out 1067 ms 6632 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2128 KB Output is correct
2 Correct 115 ms 2128 KB Output is correct
3 Correct 33 ms 1872 KB Output is correct
4 Correct 177 ms 2396 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 948 KB Output is correct
2 Correct 48 ms 844 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 52 ms 592 KB Output is correct
5 Correct 84 ms 828 KB Output is correct
6 Correct 22 ms 628 KB Output is correct
7 Correct 90 ms 860 KB Output is correct
8 Correct 81 ms 848 KB Output is correct

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 4 ms 2128 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 46 ms 2128 KB Output is correct
7 Correct 22 ms 1872 KB Output is correct
8 Correct 64 ms 2128 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 56 ms 2128 KB Output is correct
12 Correct 22 ms 1872 KB Output is correct
13 Correct 63 ms 2128 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 49 ms 5316 KB Output is correct
17 Correct 7 ms 1872 KB Output is correct
18 Correct 15 ms 2764 KB Output is correct
19 Execution timed out 1067 ms 6632 KB Time limit exceeded
20 Halted 0 ms 0 KB -