oj.uz

Submission #931409

# Submission time Handle Problem Language Result Execution time Memory
931409 2024-02-21T18:15:39 Z PieArmy Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 190024 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;
            if(mp[C[komsu[pos][i].sc]]-P[komsu[pos][i].sc]<P[komsu[pos][i].sc]){
                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())});
            }
            else{
                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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 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 8 ms 1116 KB Output is correct
8 Correct 4 ms 856 KB Output is correct
9 Correct 1026 ms 47540 KB Output is correct
10 Correct 397 ms 24896 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Incorrect 74 ms 13676 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 40380 KB Output is correct
2 Correct 150 ms 12624 KB Output is correct
3 Execution timed out 3036 ms 190024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 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 8 ms 1116 KB Output is correct
8 Correct 4 ms 856 KB Output is correct
9 Correct 1026 ms 47540 KB Output is correct
10 Correct 397 ms 24896 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Incorrect 74 ms 13676 KB Output isn't correct
13 Halted 0 ms 0 KB -