oj.uz

답안 #415579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415579 2021-06-01T08:52:15 Z amoo_safar Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 73764 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 4e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int to[N], c[N], p[N], m = 2;
vector<int> G[N];

ll dis[2][N]; // 0 -> Null, 1 -> fixed

ll sm[N], cost[N];

int nl[N];
int la[N], cn[N];


map<int, int> mp[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, _m;
	cin >> n >> _m;
	int u, v;
	for(int i = 0; i < _m; i++){
		cin >> u >> v >> c[m] >> p[m];
		
		c[m + 1] = c[m]; p[m + 1] = p[m];
		to[m] = v; to[m + 1] = u;
		
		G[u].pb(m);
		G[v].pb(m + 1);

		m += 2;
	}
	to[0] = 1;
	to[1] = -1;
	c[0] = c[1] = _m + 2;


	for(int i = 1; i <= n; i++){
		for(auto e : G[i]){
			sm[c[e]] += p[e];
		}
		for(auto e : G[i]){
			cost[e] = sm[c[e]] - p[e];
		}
		for(auto e : G[i]){
			sm[c[e]] -= p[e];
		}
	}

	memset(dis, 31, sizeof dis);

	dis[0][0] = 0;
	set< pair<ll, pii> > st;
	st.insert({0, {0, 0}});
	ll ans = Inf;
	
	memset(la, -1, sizeof la);

	while(!st.empty()){
		pii fr = st.begin() -> S;
		st.erase(st.begin());
		ll d = dis[fr.F][fr.S];
		int ed = fr.S;
		u = to[fr.S];
		
		if(fr.F == 0){
			mp[u][c[ed]] ++;
			if(mp[u][c[ed]] > 2) continue;
			// 	mp[u][c[ed]] ++;
			// } else {

			// }
		} else {

			cn[u] ++;
			if(cn[u] > 2) continue;
			// if(la[u] == c[ed]) continue;
			// la[u] = c[ed];
			// cn[u] ++;
			// if(cn[u] > 2) continue;
		}
		// cerr << "## " << d << ' ' << ed << ' ' << u << '\n';
		for(auto nx : G[u]){
			if((nx ^ 1) == ed) continue;
			// cerr << "! " << ' ' << nx << '\n';
			for(int ch = 0; ch < 2; ch ++){
				ll cst = cost[nx];
				if(ch == 0) cst = p[nx];
				if(ch == 1 && c[ed] == c[nx] && fr.F == 0)
					cst -= p[ed];
				// cerr << "^ " << dis[c]
				if(dis[ch][nx] > d + cst){
					st.erase({dis[ch][nx], {ch, nx}});
					dis[ch][nx] = d + cst;
					st.insert({dis[ch][nx], {ch, nx}});
				}
			}
		}
		if(u == n) ans = min(ans, d);
	}
	cout << (ans == Inf ? -1 : ans) << '\n';
	return 0;
}

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 36300 KB Output is correct
2 Correct 24 ms 36252 KB Output is correct
3 Correct 25 ms 36360 KB Output is correct
4 Correct 24 ms 36300 KB Output is correct
5 Correct 25 ms 36300 KB Output is correct
6 Correct 23 ms 36300 KB Output is correct
7 Correct 22 ms 36632 KB Output is correct
8 Correct 24 ms 36420 KB Output is correct
9 Correct 37 ms 36760 KB Output is correct
10 Correct 40 ms 36824 KB Output is correct
11 Correct 28 ms 36812 KB Output is correct
12 Incorrect 28 ms 36684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 723 ms 56044 KB Output is correct
2 Correct 196 ms 44808 KB Output is correct
3 Correct 1367 ms 73764 KB Output is correct
4 Correct 334 ms 48464 KB Output is correct
5 Execution timed out 3080 ms 72104 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 36300 KB Output is correct
2 Correct 24 ms 36252 KB Output is correct
3 Correct 25 ms 36360 KB Output is correct
4 Correct 24 ms 36300 KB Output is correct
5 Correct 25 ms 36300 KB Output is correct
6 Correct 23 ms 36300 KB Output is correct
7 Correct 22 ms 36632 KB Output is correct
8 Correct 24 ms 36420 KB Output is correct
9 Correct 37 ms 36760 KB Output is correct
10 Correct 40 ms 36824 KB Output is correct
11 Correct 28 ms 36812 KB Output is correct
12 Incorrect 28 ms 36684 KB Output isn't correct
13 Halted 0 ms 0 KB -