oj.uz

답안 #446834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446834 2021-07-23T12:15:57 Z Nima_Naderi Traffic (CEOI11_tra) C++14
48 / 100
 5000 ms 86764 KB 
//In the name of God
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef int ll;
const ll MXN = 3e5 + 10;
ll n, m, h, w, ts;
ll te[MXN], tw[MXN], dp[MXN], cmp[MXN], comp[MXN];
vector<ll> adj[MXN], adt[MXN], Top, G[MXN], Gp[MXN], C[MXN];
bool east[MXN], west[MXN], vis[MXN], is[MXN];
vector<pair<ll, ll>> ANS;
bool kr[MXN];
inline void add_edge(ll u, ll v){
	adj[u].push_back(v);
	adt[v].push_back(u);
}
void dfs(ll u){
	vis[u] = 1;
	for(auto v : adj[u]){
			if(!vis[v]) dfs(v);
	}
	Top.push_back(u);
}
void sfd(ll u, ll c){
	comp[u] = c, C[c].push_back(u);
	for(auto v : adt[u]){
		if(!comp[v]) sfd(v, c);
	}
}
vector<ll> V;
ll DFS(ll u){
	ll res = te[u];
	vis[u] = 1; V.push_back(u);
	for(auto v : G[u]){
		if(!vis[v]) res += DFS(v);
	}
	return res;
}
void SFD(ll u, ll x){
	vis[u] = 1; dp[u] += x;
	V.push_back(u);
	for(auto v : Gp[u]){
		if(!vis[v] && kr[v]) SFD(v, x);
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> h >> w;
	for(int i = 1; i <= n; i ++){
		ll x, y; cin >> x >> y;
		east[i] = (x == h), west[i] = (x == 0);
		cmp[i] = -y;
	}
	for(int i = 1; i <= m; i ++){
		ll u, v, f; cin >> u >> v >> f;
		add_edge(u, v);
		if(f > 1) add_edge(v, u);
	}
	for(int i = 1; i <= n; i ++){
		if(!vis[i]) dfs(i);
	}
	reverse(Top.begin(), Top.end());
	for(int j = 1; j <= n; j ++){
		ll i = Top[j - 1];
		if(!comp[i]) sfd(i, ++ ts);
	}
	for(int i = 1; i <= n; i ++){
		te[comp[i]] += east[i];
		tw[comp[i]] += west[i];
	}
	for(int i = 1; i <= ts; i ++){
		for(auto u : C[i]){
			for(auto v : adj[u]){
				if(comp[v] != i && !is[comp[v]]){
					is[comp[v]] = 1;
					G[i].push_back(comp[v]);
					Gp[comp[v]].push_back(i);
				}
			}
		}
		for(auto X : G[i]) is[X] = 0;
	}
	for(int i = 1; i <= ts; i ++){
		kr[i] = (tw[i] > 0);
		if(kr[i]) continue;
		for(auto X : Gp[i]){
			if(kr[X]){
				kr[i] = 1;
				break;
			}
		}
	}
	/*
		cout << ts << '\n';
		cout << "comps : \n";
		for(int i = 1; i <= n; i ++){
			cout << comp[i] << ' ';
		} cout << '\n';
		cout << "edges of scc : \n";
		for(int i = 1; i <= ts; i ++){
			cout << "scc " << i << " : \n";
			cout << "te = " << te[i] << '\n';
			for(auto j : G[i]) cout << j << ' ';
			cout << '\n';
		}
	 */
	fill(vis, vis + ts + 1, 0);
	/*
	for(int i = 1; i <= ts; i ++){
		//dp[i] = te[i];
		//for(auto j : G[i]) dp[i] += dp[j];
			if(G[i].size() <= 1){
			dp[i] = te[i];
			if(G[i].size()) dp[i] += dp[G[i][0]];
			continue;
		}
		dp[i] = DFS(i);
		for(auto X : V) vis[X] = 0;
		V.clear();
	}
	*/
	for(int i = 1; i <= ts; i ++){
		if(te[i]){
			SFD(i, te[i]);
			for(auto X : V) vis[X] = 0;
			V.clear();
		}
	}
	for(int i = 1; i <= n; i ++){
		if(west[i]){
			ANS.push_back({cmp[i], dp[comp[i]]});
		}
	}
	sort(ANS.begin(), ANS.end());
	for(auto X : ANS) cout << X.second << '\n';
	return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 35532 KB Output is correct
2 Correct 26 ms 35496 KB Output is correct
3 Correct 22 ms 35532 KB Output is correct
4 Correct 22 ms 35496 KB Output is correct
5 Correct 23 ms 35528 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 22 ms 35628 KB Output is correct
3 Correct 21 ms 35624 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Correct 24 ms 35588 KB Output is correct
3 Correct 22 ms 35660 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35916 KB Output is correct
2 Correct 48 ms 36400 KB Output is correct
3 Correct 29 ms 36120 KB Output is correct

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 38840 KB Output is correct
2 Correct 2843 ms 44176 KB Output is correct
3 Correct 61 ms 39620 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 40884 KB Output is correct
2 Correct 4090 ms 45948 KB Output is correct
3 Correct 109 ms 45516 KB Output is correct

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 47420 KB Output is correct
2 Execution timed out 5086 ms 54700 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 46116 KB Output is correct
2 Execution timed out 5099 ms 52080 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 55856 KB Output is correct
2 Execution timed out 5054 ms 67440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 70580 KB Output is correct
2 Execution timed out 5062 ms 83456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 933 ms 65416 KB Output is correct
2 Execution timed out 5080 ms 85748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 64768 KB Output is correct
2 Execution timed out 5044 ms 86764 KB Time limit exceeded
3 Halted 0 ms 0 KB -