oj.uz

Submission #382286

# Submission time Handle Problem Language Result Execution time Memory
382286 2021-03-27T00:40:58 Z ignaciocanta Robot (JOI21_ho_t4) C++14
100 / 100
 1135 ms 85532 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using tint = long long;
using ld = long double;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
using pi = pair<int,int>;
using pl = pair<tint,tint>;
using vi = vector<int>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vl = vector<tint>;
using vb = vector<bool>;
 
#define pb push_back
#define pf push_front
#define rsz resize
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sz(x) (int)(x).size()
#define ins insert
 
#define f first
#define s second
#define mp make_pair
 
#define DBG(x) cerr << #x << " = " << x << endl;
 
const int MOD = 1e9+9; //change this
const tint mod = 998244353;
const int MX = 1e5+5;
const tint INF = 1e18; 
const int inf = 2e9;
const ld PI = acos(ld(-1)); 
const ld eps = 1e-5;
 
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
 
template<class T> void remDup(vector<T> &v){ 
    sort(all(v)); v.erase(unique(all(v)),end(v));
}
 
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} 
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
 
bool valid(int x, int y, int n, int m){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int cdiv(int a, int b) { return a/b+((a^b)>0&&a%b); } //redondea p arriba
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } //redondea p abajo
 
void NACHO(string name = ""){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

struct Edge{
	int v, c; tint p;
};

struct State{
	int u; tint w; int c;
	bool operator<(const State &o)const{
		if(w == o.w){
			if(u == o.u) return c > o.c;
			return u > o.u;
		}
		return w > o.w;
	}
};

map<int, tint> costCh[MX]; // costo para cambiar todas las aristas de color j que salen de i
map<int, vector<Edge>> adj[MX]; 
tint dp[MX];
map<int, tint> dp2[MX];

int main(){
	NACHO();
	// pensemos en aristas en vez de nodos.
	// para atravesar la arista (u-v)
	// o cambio el color de esta arista
	// para que sea distinto al de aquellas incidentes
	// a u y v o cambio el color de las aristas incidentes
	// con el mismo color.
	// sea dp1[i] el minimo costo para llegar al nodo i
	// dp2[i][c] el minimo costo para llegar al nodo i si el robot acaba de
	// pasar por una arista de color c que deberia haber sido cambiada de color
	// pero no lo fue, y ademas voy a salir del nodo i con una arista de color c.
	// (asi arreglo la que no arregle y no la cuento dos veces)
	int n, m; cin >> n >> m;
	F0R(i, m){
		int u, v, c, p; cin >> u >> v >> c >> p;
		--u, --v;
		adj[u][c].pb({v, c, p});
		adj[v][c].pb({u, c, p});
		costCh[u][c] += p;
		costCh[v][c] += p;
	}
	F0R(i, n) dp[i] = INF; 
	priority_queue<State> q;
	q.push({0, 0, 0});
	dp[0] = 0;
	while(sz(q)){
		auto node = q.top();
		q.pop();
		tint w = node.w;
		int u = node.u;
		int c = node.c;
		if(c == 0){
			if(dp[u] != w) continue;
			trav(C, adj[u]){
				trav(v, C.s){
					assert(v.v != u);
					// caso 1, no giro esta arista
					// sino que las incidentes.
					tint caso1 = w+costCh[u][v.c]-v.p;
					if(caso1 < dp[v.v]){
						dp[v.v] = caso1;
						q.push({v.v, dp[v.v], 0});
					}
					// giro esta
					tint caso2 = w+v.p;
					if(caso2 < dp[v.v]){
						dp[v.v] = caso2;
						q.push({v.v, dp[v.v], 0});
					}
					// no giro ninguna y la giro luego
					tint caso3 = w;
					if(dp2[v.v].count(v.c) == 0 || caso3 < dp2[v.v][v.c]){
						dp2[v.v][v.c] = caso3;
						q.push({v.v, dp2[v.v][v.c], v.c});
					}
				}
			}
		}else{
			if(dp2[u][c] != w) continue;
			trav(v, adj[u][c]){
				// si o si tengo que girar todas las incidentes
				tint caso1 = w+costCh[u][c]-v.p;
				if(caso1 < dp[v.v]){
					dp[v.v] = caso1;
					q.push({v.v, dp[v.v], 0});
				}
			}
		}
	}
	if(dp[n-1] == INF) cout << -1 << "\n";
	else cout << dp[n-1] << "\n";
}

Compilation message

Main.cpp: In function 'void NACHO(std::string)':
Main.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14572 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 14 ms 15084 KB Output is correct
10 Correct 13 ms 15084 KB Output is correct
11 Correct 12 ms 14828 KB Output is correct
12 Correct 11 ms 14828 KB Output is correct
13 Correct 12 ms 14828 KB Output is correct
14 Correct 12 ms 14848 KB Output is correct
15 Correct 11 ms 14700 KB Output is correct
16 Correct 13 ms 14828 KB Output is correct
17 Correct 12 ms 14956 KB Output is correct
18 Correct 11 ms 14572 KB Output is correct
19 Correct 12 ms 14700 KB Output is correct
20 Correct 11 ms 14700 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 33572 KB Output is correct
2 Correct 99 ms 24228 KB Output is correct
3 Correct 242 ms 29536 KB Output is correct
4 Correct 148 ms 27172 KB Output is correct
5 Correct 1135 ms 79772 KB Output is correct
6 Correct 889 ms 73036 KB Output is correct
7 Correct 430 ms 60484 KB Output is correct
8 Correct 447 ms 50956 KB Output is correct
9 Correct 469 ms 50924 KB Output is correct
10 Correct 361 ms 48288 KB Output is correct
11 Correct 158 ms 32748 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14572 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 14 ms 15084 KB Output is correct
10 Correct 13 ms 15084 KB Output is correct
11 Correct 12 ms 14828 KB Output is correct
12 Correct 11 ms 14828 KB Output is correct
13 Correct 12 ms 14828 KB Output is correct
14 Correct 12 ms 14848 KB Output is correct
15 Correct 11 ms 14700 KB Output is correct
16 Correct 13 ms 14828 KB Output is correct
17 Correct 12 ms 14956 KB Output is correct
18 Correct 11 ms 14572 KB Output is correct
19 Correct 12 ms 14700 KB Output is correct
20 Correct 11 ms 14700 KB Output is correct
21 Correct 228 ms 33572 KB Output is correct
22 Correct 99 ms 24228 KB Output is correct
23 Correct 242 ms 29536 KB Output is correct
24 Correct 148 ms 27172 KB Output is correct
25 Correct 1135 ms 79772 KB Output is correct
26 Correct 889 ms 73036 KB Output is correct
27 Correct 430 ms 60484 KB Output is correct
28 Correct 447 ms 50956 KB Output is correct
29 Correct 469 ms 50924 KB Output is correct
30 Correct 361 ms 48288 KB Output is correct
31 Correct 158 ms 32748 KB Output is correct
32 Correct 159 ms 28772 KB Output is correct
33 Correct 186 ms 30432 KB Output is correct
34 Correct 474 ms 51100 KB Output is correct
35 Correct 370 ms 42140 KB Output is correct
36 Correct 376 ms 47692 KB Output is correct
37 Correct 427 ms 50304 KB Output is correct
38 Correct 448 ms 59972 KB Output is correct
39 Correct 177 ms 32360 KB Output is correct
40 Correct 462 ms 52332 KB Output is correct
41 Correct 497 ms 52460 KB Output is correct
42 Correct 552 ms 61776 KB Output is correct
43 Correct 276 ms 37280 KB Output is correct
44 Correct 511 ms 43152 KB Output is correct
45 Correct 359 ms 47724 KB Output is correct
46 Correct 311 ms 47980 KB Output is correct
47 Correct 405 ms 50624 KB Output is correct
48 Correct 1135 ms 85532 KB Output is correct