# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
931414 |
2024-02-21T18:25:50 Z |
PieArmy |
Robot (JOI21_ho_t4) |
C++17 |
|
844 ms |
37840 KB |
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
#define int ll
void code(){
int n,m;cin>>n>>m;
int C[m+1],P[m+1];
vector<pair<int,int>>komsu[n+1];
pair<int,int>kenar[m+1];
pair<int,int>sira[m+1];
vector<bool>dp[n+1];
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b>>C[i]>>P[i];
kenar[i].fr=a;
kenar[i].sc=b;
sira[i].fr=komsu[a].size();
sira[i].sc=komsu[b].size();
dp[a].pb(false);
dp[b].pb(false);
komsu[a].pb({b,i});
komsu[b].pb({a,i});
}
for(int i=1;i<=n;i++)
dp[i].pb(false);
priority_queue<vector<int>>pq;
pq.push({0,1,int(komsu[1].size())});
int ans=inf;
while(pq.size()){
int pos=pq.top()[1],cos=-pq.top()[0],root=pq.top()[2];
pq.pop();
if(dp[pos][root])continue;
dp[pos][root]=true;
if(pos==n){
ans=min(ans,cos);
continue;
}
map<int,int>mp;
for(int i=0;i<komsu[pos].size();i++){
if(i==root)continue;
if(root!=komsu[pos].size())
if(C[komsu[pos][root].sc]!=C[komsu[pos][i].sc])
continue;
mp[C[komsu[pos][i].sc]]+=P[komsu[pos][i].sc];
}
for(int i=0;i<komsu[pos].size();i++){
if(i==root)continue;
if(root!=komsu[pos].size())
if(C[komsu[pos][root].sc]!=C[komsu[pos][i].sc])
continue;
pq.push({-cos-mp[C[komsu[pos][i].sc]]+P[komsu[pos][i].sc],komsu[pos][i].fr,int(komsu[komsu[pos][i].fr].size())});
int nex=sira[komsu[pos][i].sc].fr;
if(kenar[komsu[pos][i].sc].fr==pos)nex=sira[komsu[pos][i].sc].sc;
pq.push({-cos-P[komsu[pos][i].sc],komsu[pos][i].fr,nex});
}
}
if(ans==inf)cout<<-1;
else cout<<ans;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
code();
return 0;
}
Compilation message
Main.cpp: In function 'void code()':
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<komsu[pos].size();i++){
| ~^~~~~~~~~~~~~~~~~~
Main.cpp:49:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if(root!=komsu[pos].size())
| ~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:54:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<komsu[pos].size();i++){
| ~^~~~~~~~~~~~~~~~~~
Main.cpp:56:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(root!=komsu[pos].size())
| ~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Incorrect |
4 ms |
1116 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
844 ms |
37840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Incorrect |
4 ms |
1116 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |