oj.uz

Submission #201130

# Submission time Handle Problem Language Result Execution time Memory
201130 2020-02-09T11:55:53 Z zscoder Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 966 ms 11540 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
set<int> S;

struct Graph
{
	struct edge
	{
		int v; ll weight; int id;
	};
	vector<vector<edge> > adj;
	int n;
	
	Graph(int _n)
	{
		adj.resize(_n);
		n = _n;
	}
	
	void addedge(int u, int v, ll c, int id)
	{
		edge tmp;
		tmp.v = v; tmp.weight = c; tmp.id=id;
		adj[u].pb(tmp);
	}
	
	void reset()
	{
		adj.clear();
	}
	
	vector<ll> dist;
	vi par;
	
	void bfs(int s)
	{
		ll INFI = ll(1e18);
		dist.assign(n, INFI);
		par.assign(n, -1);
		dist[s] = 0; par[s] = -1;
		queue<int> q; q.push(s);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			for(int i = 0; i < adj[u].size(); i++)
			{
				int v = adj[u][i].v;
				if(dist[v] >= INFI)
				{
					dist[v] = dist[u] + 1;
					par[v] = u;
					q.push(v);
				}
			}
		}
	}
	
	void bfs01(int s)
	{
		ll INFI = ll(1e18);
		dist.assign(n, INFI);
		par.assign(n, -1);
		dist[s] = 0; par[s] = -1;
		deque<int> q; q.pb(s);
		while(!q.empty())
		{
			int u = q.front(); q.pop_front();
			for(int i = 0; i < adj[u].size(); i++)
			{
				int v = adj[u][i].v; ll w = adj[u][i].weight;
				if(dist[v] >= INFI)
				{
					if(w == 1)
					{
						dist[v] = dist[u] + 1;
						par[v] = u;
						q.push_back(v);
					}
					else
					{
						dist[v] = dist[u];
						par[v] = u;
						q.push_front(v);
					}
				}
			}
		}
	}
	
	void dijkstra(int s, int mode=1)
	{
		ll INFI = ll(1e18);
		dist.clear();
		dist.assign(n, INFI);
		par.assign(n, -1);
		dist[s] = 0; par[s] = -1;
		priority_queue<ii, vector<ii>, greater<ii> > pq;
		pq.push(ii(0, s));
		while(!pq.empty())
		{
			int u = pq.top().se; ll d = pq.top().fi; pq.pop();
			for(int i = 0; i < adj[u].size(); i++)
			{
				int v = adj[u][i].v; ll w = adj[u][i].weight;
				if(d + w < dist[v])
				{
					dist[v] = d + w;
					par[v] = u;
					//cerr<<"ADD "<<adj[u][i].id<<'\n';
					if(mode) S.insert(adj[u][i].id);
					pq.push(ii(dist[v], v));
				}
			}
		}
	}
	
	vector<vector<ll> > d;
	
	void Floyd()
	{
		ll INFIN = ll(1e18);
		d.resize(n);
		for(int i = 0; i < n; i++)
		{
			d[i].assign(n, INFIN);
		}
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < adj[i].size(); j++)
			{
				d[i][adj[i][j].v] = min(d[i][adj[i][j].v],adj[i][j].weight);
			}
			d[i][i] = 0;
		}
		for(int k = 0; k < n; k++)
		{
			for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
	}
};

ll D[55555];
vector<pair<ii,ii> > edges;
int n,m; 
ll res=ll(1e18);

void test(int id)
{
	Graph G(n);
	for(int i=0;i<m;i++)
	{
		int u=edges[i].fi.fi; int v=edges[i].fi.se;
		if(i==id) swap(u,v);
		G.addedge(u,v,edges[i].se.fi,edges[i].se.se);
	}
	G.dijkstra(0,0);
	ll ans = G.dist[n-1];
	G.dijkstra(n-1,0);
	ans+=G.dist[0];
	ans+=D[id];
	res=min(res,ans);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	Graph ori(n),rev(n),oriunw(n),revunw(n);
	vector<ii> VV;
	int all0=1;
	for(int i=0;i<m;i++)
	{
		int u,v,c,d;
		cin>>u>>v>>c>>d;
		if(c!=0) all0=0;
		VV.pb({d,i});
		u--; v--;
		D[i]=d;
		edges.pb({{u,v},{c,d}});
		ori.addedge(u,v,c,i);
		oriunw.addedge(u,v,1,i);
		rev.addedge(v,u,c,i);
		revunw.addedge(v,u,1,i);
	}
	int sub2=1;
	if(m%2==0)
	{
		for(int i=0;i<m;i+=2)
		{
			int a1 = edges[i].se.se;
			int a2 = edges[i+1].se.se;
			edges[i].se.se=edges[i+1].se.se=0;
			if(edges[i]!=edges[i+1]) sub2=0;
			edges[i].se.se=a1; edges[i+1].se.se=a2;
		}
	}
	else sub2=0;
	ori.Floyd();
	ori.dijkstra(0);
	sort(VV.begin(),VV.end());
	//for(int i=0;i<min(100,m);i++) S.insert(VV[i].se);
	ll as = ori.dist[n-1];
	ori.dijkstra(n-1);
	as+=ori.dist[0];
	rev.dijkstra(n-1);
	res=min(res,as);
	//assert(sub2);
	if(sub2)
	{
		for(auto E:edges)
		{
			int u=E.fi.fi; int v=E.fi.se; 
			ll c=E.se.fi; ll d=E.se.se;
			//should i add the edge v->u
			res=min(res,d+ori.d[0][n-1]+ori.d[n-1][v]+c+ori.d[u][0]);
			res=min(res,d+ori.d[0][v]+c+ori.d[u][n-1]+ori.d[n-1][0]);
			res=min(res,d+ori.d[0][v]+c+ori.d[u][n-1]+ori.d[n-1][v]+c+ori.d[u][0]);
			res=min(res,ori.d[0][n-1]+ori.d[n-1][0]);
		}
	}
	else
	{
		for(int s:S) 
		{
			test(s);
		}
	}
	if(res>=ll(1e18)) res=-1;
	cout<<res<<'\n';
}

Compilation message

ho_t4.cpp: In member function 'void Graph::bfs(int)':
ho_t4.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < adj[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~
ho_t4.cpp: In member function 'void Graph::bfs01(int)':
ho_t4.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < adj[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~
ho_t4.cpp: In member function 'void Graph::dijkstra(int, int)':
ho_t4.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < adj[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~
ho_t4.cpp: In member function 'void Graph::Floyd()':
ho_t4.cpp:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < adj[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:193:6: warning: variable 'all0' set but not used [-Wunused-but-set-variable]
  int all0=1;
      ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 888 KB Output is correct
2 Correct 15 ms 760 KB Output is correct
3 Correct 81 ms 976 KB Output is correct
4 Correct 87 ms 888 KB Output is correct
5 Correct 19 ms 504 KB Output is correct
6 Correct 15 ms 760 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 296 KB Output is correct
9 Incorrect 6 ms 636 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9316 KB Output is correct
2 Correct 54 ms 9184 KB Output is correct
3 Correct 52 ms 9320 KB Output is correct
4 Correct 16 ms 1016 KB Output is correct
5 Correct 14 ms 888 KB Output is correct
6 Correct 14 ms 760 KB Output is correct
7 Correct 14 ms 760 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 50 ms 9444 KB Output is correct
10 Correct 51 ms 9444 KB Output is correct
11 Correct 51 ms 9188 KB Output is correct
12 Correct 51 ms 9188 KB Output is correct
13 Correct 52 ms 9316 KB Output is correct
14 Correct 54 ms 10212 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 888 KB Output is correct
2 Correct 17 ms 760 KB Output is correct
3 Correct 821 ms 8584 KB Output is correct
4 Correct 16 ms 760 KB Output is correct
5 Correct 966 ms 10908 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Incorrect 460 ms 11540 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 888 KB Output is correct
2 Correct 15 ms 760 KB Output is correct
3 Correct 81 ms 976 KB Output is correct
4 Correct 87 ms 888 KB Output is correct
5 Correct 19 ms 504 KB Output is correct
6 Correct 15 ms 760 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 296 KB Output is correct
9 Incorrect 6 ms 636 KB Output isn't correct
10 Halted 0 ms 0 KB -