Submission #937224

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
937224	2024-03-03 16:24:22	Litusiano	Voting Cities (NOI22_votingcity)	C++17	100 / 100	245 ms	3380 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
vector<vector<pair<int,int>>> G;
vector<vector<int>> dp;
vector<int> ct;
void dijkstra(int s){ 
  priority_queue<tuple<int,int,int>>pq;
  pq.push({0,s,0}); // cost node msk
  while(!pq.empty()){
    int w,u,msk; tie(w,u,msk) = pq.top(); pq.pop();
    if(w > dp[u][msk]) continue;
    for(auto p : G[u]){
      int v = p.first; int cost = p.second;
      for(int i = 0; i<6; i++){
        if(i > 0 && msk & (1<<(i-1)) || ct[i] == -1) {
          continue;
        }
        int t = cost-(i*(cost/10)) + ct[i];
        if(t > cost) continue;
        if(!i){
          if(dp[v][msk] > dp[u][msk] + t){
            dp[v][msk] = dp[u][msk]+t;
            pq.push({-dp[v][msk],v,msk});
          }
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

Main.cpp: In function 'void dijkstra(long long int)':
Main.cpp:20:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     if(i > 0 && msk & (1<<(i-1)) || ct[i] == -1) {
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50