oj.uz

Submission #158812

# Submission time Handle Problem Language Result Execution time Memory
158812 2019-10-18T21:11:25 Z janchomath Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 817 ms 37004 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 200005
#define mp make_pair
using namespace std;
ll ds[N],dt[N],du[N],df[N],raod[N],s,t,u,f,n,m,dp1[N],dp2[N],p[N],ans=100000000000000;
vector<pair<ll,ll> >v[N];
vector<ll>g[N],rev[N];
void dj(ll k){
	vector<ll> d (n + 1, 100000000000000);
	d[k] = 0;
	set < pair<ll,ll> > q;
	q.insert (make_pair (d[k], k));
	while(!q.empty()) {
		ll x = q.begin()->s;
		q.erase (q.begin());
		for (int i=0; i<v[x].size(); i++) {
			ll to = v[x][i].f,
				len = v[x][i].s;
			if (d[x] + len < d[to]) {
				if(q.find(mp(d[to] , to)) != q.end())q.erase(make_pair (d[to], to));
				d[to] = d[x] + len;
				q.insert(make_pair (d[to], to));
			}
		}
	}
    for(int i=1; i<=n; i++){
        p[i] = d[i];
     }
}
void dfs(ll x){
    dp1[x] = 100000000000000;
    dp2[x] = 100000000000000;
    for(int i=0; i<rev[x].size(); i++)
        dp1[x] = min(dp1[x] , dp1[rev[x][i]]);
    dp1[x] = min(dp1[x] , du[x]);
    ans = min(ans , dp1[x] + df[x]);
    for(int i=0; i<rev[x].size(); i++)
        dp2[x] = min(dp2[x] , dp2[rev[x][i]]);
    dp2[x] = min(dp2[x] , df[x]);
    ans = min(ans , dp2[x] + df[x]);
    ans = min(ans , dp2[x] + du[x]);
    for(int i=0; i<g[x].size(); i++)
        if(raod[g[x][i]] <= 1)dfs(g[x][i]);
        else raod[g[x][i]]--;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> s >> t >> u >> f;
    
    for(int i=1; i<=m; i++){
        int x,y,z;
        cin >> x >> y >> z;
        v[x].pb(mp(y , z));
        v[y].pb(mp(x , z));
    }
    
    dj(s);
    for(int i=1; i<=n; i++)
        ds[i] = p[i];
    dj(t);
    for(int i=1; i<=n; i++)
        dt[i] = p[i];
    dj(u);
    for(int i=1; i<=n; i++)
        du[i] = p[i];
    dj(f);
    for(int i=1; i<=n; i++)
        df[i] = p[i];
    for(int i=1; i<=n; i++)
        for(int j=0; j<v[i].size(); j++)
            if(ds[i] + v[i][j].s + dt[v[i][j].f] == ds[t]){
                g[i].pb(v[i][j].f),
                rev[v[i][j].f].pb(i);
            }
    for(int i=1; i<=n; i++)
        raod[i] = (ll)rev[i].size();
    ans = du[f];
    dfs(s);
    
    cout << ans << endl;
    
    
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dj(long long int)':
commuter_pass.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<g[x].size(); i++)
                  ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 31696 KB Output is correct
2 Correct 605 ms 32504 KB Output is correct
3 Correct 702 ms 37004 KB Output is correct
4 Correct 593 ms 31708 KB Output is correct
5 Correct 563 ms 33812 KB Output is correct
6 Correct 817 ms 32052 KB Output is correct
7 Correct 680 ms 34488 KB Output is correct
8 Correct 590 ms 33920 KB Output is correct
9 Correct 552 ms 30660 KB Output is correct
10 Correct 426 ms 31028 KB Output is correct
11 Correct 174 ms 29528 KB Output is correct
12 Correct 621 ms 30592 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 33000 KB Output is correct
2 Correct 692 ms 33448 KB Output is correct
3 Incorrect 671 ms 33024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15992 KB Output is correct
2 Correct 20 ms 14568 KB Output is correct
3 Incorrect 16 ms 14584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 31696 KB Output is correct
2 Correct 605 ms 32504 KB Output is correct
3 Correct 702 ms 37004 KB Output is correct
4 Correct 593 ms 31708 KB Output is correct
5 Correct 563 ms 33812 KB Output is correct
6 Correct 817 ms 32052 KB Output is correct
7 Correct 680 ms 34488 KB Output is correct
8 Correct 590 ms 33920 KB Output is correct
9 Correct 552 ms 30660 KB Output is correct
10 Correct 426 ms 31028 KB Output is correct
11 Correct 174 ms 29528 KB Output is correct
12 Correct 621 ms 30592 KB Output is correct
13 Correct 701 ms 33000 KB Output is correct
14 Correct 692 ms 33448 KB Output is correct
15 Incorrect 671 ms 33024 KB Output isn't correct
16 Halted 0 ms 0 KB -