oj.uz

Submission #449342

# Submission time Handle Problem Language Result Execution time Memory
449342 2021-08-02T05:50:57 Z arnob918 Robot (JOI21_ho_t4) C++14
0 / 100
 130 ms 16132 KB 
#include    <bits/stdc++.h>
#include    <stdio.h>
#include    <ext/pb_ds/assoc_container.hpp>// For pbds.Don't use tree as variable name.
#include    <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb          push_back
#define eb          emplace_back
#define mem(x,i)    memset(x,i,sizeof(x))
#define ff          first
#define ss          second
#define all(x)      x.begin(),x.end()
#define Q 			int t; scanf("%d", &t); for(int q=1; q<=t; q++)

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;//%Lf
typedef pair<ll, ll> pi;

template <typename T>  using orderedSet = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
    //order_of_key(k) - number of element strictly less than k.
    //find_by_order(k) - k'th element in set.(0 indexed)(iterator)

                            /* Debug Tools */
#define error(args...) \
{ \
    string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
    stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);\
}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr<< *it << " = " << a <<",\n"[++it==istream_iterator<string>()];
    err(it, args...);
}

const int MOD = 1e9+7 ; //For big mod
template<typename T>inline T gcd(T a, T b){T c;while (b){c = b;b = a % b;a = c;}return a;} // better than __gcd
ll powmod(ll a,ll b){ll res=1;a%=MOD;if(b<0) return 0;for(; b; b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

const int xx[] = {+1, -1, +0, +0};//, +1, +1, -1, -1};// exclude last four when side adjacent
const int yy[] = {+0, +0, +1, -1};//, +1, -1, +1, -1};
const int INF    = 0x3f3f3f3f;// useful for memset
const ll LL_INF  = 0x3f3f3f3f3f3f3f3f;
const double PI  = acos(-1.0);
const double eps = 1e-9;
const int mxn     = 1e5+5; //CHECK here for every problem
const int mod    = 1e9+7;

int n, m;
vector<ll> adj[mxn], col[mxn], cost[mxn];

int main()
{
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		ll u, v, c, w;
		scanf("%lld %lld %lld %lld", &u, &v, &c, &w);
		adj[u].pb(v);
		adj[v].pb(u);
		col[u].pb(c);
		col[v].pb(c);
		cost[u].pb(w);
		cost[v].pb(w);
	}
	vector<ll> dis(n+4, LL_INF);
	priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push({0, {1, 0}});
	while(!pq.empty()){
		pair<ll, pi> tp = pq.top();
		pq.pop();
		int u = tp.ss.ff;
		int p = tp.ss.ss;
		ll cc = tp.ff;
		if(dis[u] < cc) continue;
		map<int, int> mp;
		for(int i=0; i<(int)adj[u].size(); i++){
			int v = adj[u][i];
			if(v != p){
				mp[col[u][i]]++;
			}
		}
		for(int i=0; i<(int)adj[u].size(); i++){
			int v = adj[u][i];
			if(v == p) continue;
			ll nc = 0;
			if(mp[col[u][i]] > 1) nc = cost[u][i];
			if(cc+nc < dis[v]){
				dis[v] = cc+nc;
				pq.push({cc+nc, {v, u}});
			}
		}
	}
	ll ans = dis[n];
	if(ans == LL_INF) ans = -1;
	printf("%lld\n", ans);
			
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%lld %lld %lld %lld", &u, &v, &c, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7336 KB Output is correct
3 Correct 4 ms 7336 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Incorrect 7 ms 7416 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 16132 KB Output is correct
2 Incorrect 43 ms 11472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7336 KB Output is correct
3 Correct 4 ms 7336 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Incorrect 7 ms 7416 KB Output isn't correct
8 Halted 0 ms 0 KB -