oj.uz

Submission #937221

# Submission time Handle Problem Language Result Execution time Memory
937221 2024-03-03T16:20:39 Z Litusiano Voting Cities (NOI22_votingcity) C++17
45 / 100
 1000 ms 7704 KB 
#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(!i){
					if(dp[v][msk] > dp[u][msk] + t){
						dp[v][msk] = dp[u][msk]+t;
						pq.push({-dp[v][msk],v,msk});
					}
				}
				else{
					if(dp[v][msk ^ (1<<(i-1))] > dp[u][msk] + t){
						dp[v][msk ^ (1<<(i-1))] = dp[u][msk]+t;
						pq.push({-dp[u][msk]-t, v,(msk ^ (1<<(i-1))) }); 
					}
				}
			}
		}
	}
}

signed main(){
  	ios_base::sync_with_stdio(0);
  	cin.tie(0);
	int n,e,k; cin>>n>>e>>k;
	vector<int> good;
	for(int i = 0; i<k; i++){
		int x; cin>>x;
		good.push_back(x);
	}
	G.resize(n+1);
	for(int i = 0; i<e; i++){
		int u,v,w; cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	int q; cin>>q;
	while(q--){
		ct.assign(6,0);
		dp.assign(n+1, vector<int>(32, inf));
		int s; cin>>s;
		// cerr<<"S: "<<s<<endl;
		for(int i = 1; i<=5; i++) cin>>ct[i];
		dp[s][0] = 0;
		dijkstra(s);
		int ans = inf;
		for(int i = 0; i<k; i++){
			// cerr<<good[i]<<endl;
			for(int j = 0; j<32; j++){
				ans = min(ans,dp[good[i]][j]);
			}
		}
		if(ans == inf) ans = -1;
		cout<<ans<<"\n";
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 50 ms 2488 KB Output is correct
7 Correct 15 ms 2140 KB Output is correct
8 Correct 73 ms 2396 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 50 ms 2488 KB Output is correct
7 Correct 15 ms 2140 KB Output is correct
8 Correct 73 ms 2396 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 59 ms 2648 KB Output is correct
12 Correct 16 ms 2140 KB Output is correct
13 Correct 71 ms 2392 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 62 ms 6864 KB Output is correct
7 Correct 7 ms 2136 KB Output is correct
8 Correct 17 ms 3160 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 50 ms 2488 KB Output is correct
7 Correct 15 ms 2140 KB Output is correct
8 Correct 73 ms 2396 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 62 ms 6864 KB Output is correct
12 Correct 7 ms 2136 KB Output is correct
13 Correct 17 ms 3160 KB Output is correct
14 Execution timed out 1064 ms 7704 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2668 KB Output is correct
2 Correct 136 ms 2652 KB Output is correct
3 Correct 33 ms 2240 KB Output is correct
4 Correct 206 ms 2732 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 1048 KB Output is correct
2 Correct 74 ms 816 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 97 ms 684 KB Output is correct
5 Correct 138 ms 804 KB Output is correct
6 Correct 28 ms 604 KB Output is correct
7 Correct 159 ms 816 KB Output is correct
8 Correct 141 ms 844 KB Output is correct

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 2 ms 2140 KB Output is correct
3 Correct 4 ms 2416 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 50 ms 2488 KB Output is correct
7 Correct 15 ms 2140 KB Output is correct
8 Correct 73 ms 2396 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 59 ms 2648 KB Output is correct
12 Correct 16 ms 2140 KB Output is correct
13 Correct 71 ms 2392 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 62 ms 6864 KB Output is correct
17 Correct 7 ms 2136 KB Output is correct
18 Correct 17 ms 3160 KB Output is correct
19 Execution timed out 1064 ms 7704 KB Time limit exceeded
20 Halted 0 ms 0 KB -