oj.uz

Submission #758486

# Submission time Handle Problem Language Result Execution time Memory
758486 2023-06-14T16:35:59 Z 1075508020060209tc Robot (JOI21_ho_t4) C++14
24 / 100
 1200 ms 107424 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n;int m;
int ar[200005];int br[200005];int clr[200005];int wr[200005];
vector<int>e[200005];
int dis[200005];
int vis[200005];
map<int,int>mpsm[500005];
int mpf[500005];

map<int,vector<pair<int,int>>>mpe[200005];
map<int,int>mxe[200005];
signed main(){


cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i]>>clr[i]>>wr[i];
    e[ar[i]].push_back(i);
    e[br[i]].push_back(i);
    mpe[ar[i]][clr[i]].push_back({wr[i],i});
    mpe[br[i]][clr[i]].push_back({wr[i],i});
    mpsm[ar[i]][clr[i]]+=wr[i];
    mpsm[br[i]][clr[i]]+=wr[i];
}
for(int i=1;i<=n;i++){
    dis[i]=1e18;
    vis[i]=0;
    for(auto it=mpsm[i].begin();it!=mpsm[i].end();it++){
        sort(mpe[i][(*it).first].begin(),mpe[i][(*it).first].end());
    }
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dis[1]=0;
pq.push({0,1});
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]){continue;}
//    vis[nw]=1;

    for(int i=0;i<e[nw].size();i++){
        int id=e[nw][i];
        int v=ar[id]^br[id]^nw;
        //if(vis[v]){continue;}
        int w=wr[id];
      //  if(mpf[clr[id]]==1){
        //    w=0;
        //}
        if(dis[v]>dis[nw]+min(w,mpsm[nw][clr[id]]-w) ){
            dis[v]=dis[nw]+min(w,mpsm[nw][clr[id]]-w);
            pq.push({dis[v],v});
        }
        int ow=dis[nw]+w;int cnt=2;
        for(int j=0;j<mpe[v][clr[id]].size();j++){
            //    cout<<nw<<" "<<id<<endl;
            cnt--;
            if(cnt<0){break;}
            if(id!=mpe[v][clr[id]][j].second){
                int neid=mpe[v][clr[id]][j].second;
                int vv=v^ar[neid]^br[neid];
                w=mpsm[v][clr[id]]-wr[id]-wr[neid];
             //   cout<<nw<<" "<<v<<" "<<vv<<" "<<neid<<" "<<ow<<" "<<w<<endl;
                if(dis[vv]>ow+w){
                    dis[vv]=ow+w;
                    pq.push({dis[vv],vv});
                }
            }


        }

    }



}



int ans=dis[n];
if(dis[n]>=1e16){
    ans=-1;
}


cout<<ans<<endl;

}
/*
6 5
1 2 1 100000
1 3 1 1
2 6 1 1000
2 4 1 1
2 5 1 1
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:18: 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]
   44 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:57:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<mpe[v][clr[id]].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47228 KB Output is correct
2 Correct 24 ms 47256 KB Output is correct
3 Correct 24 ms 47304 KB Output is correct
4 Correct 21 ms 47240 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 23 ms 47320 KB Output is correct
7 Correct 26 ms 47444 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 27 ms 47928 KB Output is correct
10 Correct 33 ms 47764 KB Output is correct
11 Correct 28 ms 47592 KB Output is correct
12 Incorrect 27 ms 47668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 66704 KB Output is correct
2 Correct 129 ms 56908 KB Output is correct
3 Correct 497 ms 68984 KB Output is correct
4 Correct 184 ms 60596 KB Output is correct
5 Correct 1200 ms 107424 KB Output is correct
6 Correct 1160 ms 103696 KB Output is correct
7 Correct 570 ms 89796 KB Output is correct
8 Correct 635 ms 91120 KB Output is correct
9 Correct 653 ms 91044 KB Output is correct
10 Correct 516 ms 82568 KB Output is correct
11 Correct 258 ms 72300 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47228 KB Output is correct
2 Correct 24 ms 47256 KB Output is correct
3 Correct 24 ms 47304 KB Output is correct
4 Correct 21 ms 47240 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 23 ms 47320 KB Output is correct
7 Correct 26 ms 47444 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 27 ms 47928 KB Output is correct
10 Correct 33 ms 47764 KB Output is correct
11 Correct 28 ms 47592 KB Output is correct
12 Incorrect 27 ms 47668 KB Output isn't correct
13 Halted 0 ms 0 KB -