oj.uz

Submission #931415

# Submission time Handle Problem Language Result Execution time Memory
931415 2024-02-21T18:27:08 Z PieArmy Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 394848 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;
            mp[C[komsu[pos][i].sc]]+=P[komsu[pos][i].sc];
        }
        for(int i=0;i<komsu[pos].size();i++){
            if(i==root)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:51: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]
   51 |         for(int i=0;i<komsu[pos].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 21 ms 3092 KB Output is correct
8 Correct 8 ms 1688 KB Output is correct
9 Correct 2759 ms 108272 KB Output is correct
10 Correct 1717 ms 55012 KB Output is correct
11 Execution timed out 3041 ms 170920 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2449 ms 92848 KB Output is correct
2 Correct 491 ms 27572 KB Output is correct
3 Execution timed out 3032 ms 394848 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 21 ms 3092 KB Output is correct
8 Correct 8 ms 1688 KB Output is correct
9 Correct 2759 ms 108272 KB Output is correct
10 Correct 1717 ms 55012 KB Output is correct
11 Execution timed out 3041 ms 170920 KB Time limit exceeded
12 Halted 0 ms 0 KB -