Submission #777311

#TimeUsernameProblemLanguageResultExecution timeMemory
777311yeysoCyberland (APIO23_cyberland)C++17
21 / 100
43 ms14904 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #include <vector> double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<vector<long long>> adj(N, vector<long long>()); vector<vector<long long>> dma(N, vector<long long>()); for(long long i = 0; i < M; i ++){ adj[x[i]].push_back(y[i]); adj[y[i]].push_back(x[i]); dma[x[i]].push_back(c[i]); dma[y[i]].push_back(c[i]); } queue<pair<long long, long long>> q; q.push({0, H}); vector<long long> v(N, 0); vector<long long> d(N, LONG_LONG_MAX / 2); d[H] = 0; long long node, dist; while(!q.empty()){ node = q.front().second; dist = q.front().first; q.pop(); if(!v[node]){ v[node] = 1; for(long long i = 0; i < adj[node].size(); i ++){ d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]); q.push({dist + dma[node][i], adj[node][i]}); } } } q.push({0, 0}); vector<long long> v2(N, 0); v2[H] = 1; while(!q.empty()){ node = q.front().second; q.pop(); if(!v2[node]){ v2[node] = 1; for(long long i = 0; i < adj[node].size(); i ++){ q.push({0, adj[node][i]}); } } } long long lowest = d[0]; for(long long i = 0; i < d.size(); i ++){ if(d[i] < lowest and v2[i] == 1 and arr[i] == 0){ lowest = d[i]; } } if(lowest >= LONG_LONG_MAX / 2){ lowest = -1; } return lowest; } /* g++ -std=gnu++17 -O2 -Wall -pipe -static -o cyberland stub.cpp cyberland.cpp 1 10 9 10 6 1 1 0 1 2 2 1 0 2 1 0 1 3 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 1 3 2 30 2 1 0 1 1 2 12 2 0 4 */

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:31:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
cyberland.cpp:45:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
cyberland.cpp:51:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(long long i = 0; i < d.size(); i ++){
      |                          ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...