Submission #1117519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117519		Szymon_Pilipczuk	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	634 ms	50412 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
long long inf = (long long) 1000000000*1000000000;
long long ans;
unordered_set<int> se;
long long od[2][100000];
vector<vector<long long>> p;
vector<vector<vector<long long>>> gr;
long long dis[100000];
priority_queue<vector<long long>> pq;
void dk(long long c,int v,int st)
{
    for(int i = 0;i<gr[v].size();i++)
    {
        if(od[st][gr[v][i][0]] > c+gr[v][i][1])
        {
            pq.push({-1*(c+gr[v][i][1]),gr[v][i][0],st});
            od[st][gr[v][i][0]] = c+gr[v][i][1];
        }
    }
}
void dk2(long long c,int v)
{
    for(int i = 0;i<gr[v].size();i++)
    {
        if(dis[gr[v][i][0]] > c+gr[v][i][1])
        {
            pq.push({-1*(c+gr[v][i][1]),gr[v][i][0]});
            dis[gr[v][i][0]] = c+gr[v][i][1];
            p[gr[v][i][0]].clear();
        }
        if(dis[gr[v][i][0]] == c+gr[v][i][1])
        {
            p[gr[v][i][0]].push_back(v);
        }
    }
}
long long par[100000][2];
void dk3(long long c,int v)
{
    ans = min(ans,par[v][0]+od[1][v]);
    ans = min(ans,par[v][1]+od[0][v]);
    par[v][0] = min(par[v][0],od[0][v]);
    par[v][1] = min(par[v][1],od[1][v]);
    for(int i = 0;i<gr[v].size();i++)
    {
        if(se.find(gr[v][i][0])!= se.end())
        {
            if(dis[gr[v][i][0]] > c+gr[v][i][1])
            {
                pq.push({-1*(c+gr[v][i][1]),gr[v][i][0]});
                dis[gr[v][i][0]] = c+gr[v][i][1];
            }
            if(dis[gr[v][i][0]] == c+gr[v][i][1])
            {
                par[gr[v][i][0]][0] = min(par[gr[v][i][0]][0],par[v][0]);
                par[gr[v][i][0]][1] = min(par[gr[v][i][0]][1],par[v][1]);
            }
        }
    }
}
int main()
{
  ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int s,t,u,v;
    cin>>s>>t>>u>>v;
    s--;t--;u--;v--;
    for(int i = 0;i<n;i++)
    {
        od[0][i] = inf;
        od[1][i] = inf;
        dis[i] = inf;
        par[i][0] = inf;
        par[i][1] = inf;
    }
    od[0][u] = 0;
    od[1][v] = 0;
    dis[s] = 0;
    //par[u][0] = 0;
    //par[v][0] = 0;
    p.resize(n);
    gr.resize(n);
    for(int i = 0; i < m; i++)
    {
        int a,b;
        long long c;
        cin>>a>>b>>c;
        a--;b--;
        gr[a].push_back({b,c});
        gr[b].push_back({a,c});
    }
    pq.push({0,u,0});
    pq.push({0,v,1});
    while(!pq.empty())
    {
        long long a = pq.top()[0]*-1;
        int b = pq.top()[1];
        int c = pq.top()[2];
        pq.pop();
        dk(a,b,c);
    }
    pq.push({0,s});
    while(!pq.empty())
    {
        long long a = pq.top()[0]*-1;
        int b = pq.top()[1];
        pq.pop();
        dk2(a,b);
    }
    queue<int> pop;
    pop.push(t);
    while(!pop.empty())
    {
        int q = pop.front();
        pop.pop();
        se.insert(q);
        for(int i = 0;i<p[q].size();i++)
        {
            if(se.find(p[q][i]) == se.end())
            {
                pop.push(p[q][i]);
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        dis[i] = inf;
    }
    ans = od[0][v];
    pq.push({0,s});
    while(!pq.empty())
    {
        long long a = pq.top()[0]*-1;
        int b = pq.top()[1];
        pq.pop();
        dk3(a,b);
    }
    cout<<ans;
}
/*
8 10
7 1
4 6
2 1 21
3 2 11
1 3 30
6 4 68
7 5 87
5 6 58
4 7 8
6 2 7
1 5 71
6 8 93
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'void dk(long long int, int, int)':
commuter_pass.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0;i<gr[v].size();i++)
      |                   ~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dk2(long long int, int)':
commuter_pass.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0;i<gr[v].size();i++)
      |                   ~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dk3(long long int, int)':
commuter_pass.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0;i<gr[v].size();i++)
      |                   ~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i = 0;i<p[q].size();i++)
      |                       ~^~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45