oj.uz

Submission #392719

# Submission time Handle Problem Language Result Execution time Memory
392719 2021-04-21T14:06:40 Z junodeveloper Traffic (CEOI11_tra) C++17
100 / 100
 685 ms 71288 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
int n,m,A,B;
int X[300010],Y[300010];
int dfn[300010],dc;
int scc[300010],sc;
int ord[300010];
int D[300010][2];
int pre[300010];
bool vis[300010];
vector<int> g[300010];
vector<int> gg[300010];
vector<int> st;
vector<int> sccElem[300010];
vector<pii> L,R;
int tarjan(int u) {
	int ret=dfn[u]=++dc;
	st.pb(u);
	for(auto& v:g[u]) {
		if(dfn[v]&&!scc[v])ret=min(ret,dfn[v]);
		else if(!dfn[v])ret=min(ret,tarjan(v));
	}
	if(ret==dfn[u]) {
		++sc;
		while(!st.empty()) {
			int v=st.back();st.pop_back();
			scc[v]=sc;
			if(v==u)break;
		}
	}
	return ret;
}
void dfs(int u) {
	if(vis[u])return;
	vis[u]=true;
	for(auto& v:gg[u]) {
		dfs(v);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,j;
	cin>>n>>m>>A>>B;
	for(i=1;i<=n;i++) {
		cin>>X[i]>>Y[i];
		if(X[i]==0)L.pb({Y[i],i});
		if(X[i]==A)R.pb({Y[i],i});
	}
	sort(all(L));
	sort(all(R));
	for(i=1;i<=n;i++)ord[i]=-1;
	for(i=0;i<sz(R);i++)ord[R[i].se]=i;
	for(i=1;i<=m;i++) {
		int c,d,k;cin>>c>>d>>k;
		g[c].pb(d);
		if(k==2)g[d].pb(c);
	}
	for(i=1;i<=n;i++) {
		if(!scc[i]) {
			tarjan(i);
		}
	}
	for(i=1;i<=n;i++) {
		D[scc[i]][0]=1e9;
		D[scc[i]][1]=-1;
		sccElem[scc[i]].pb(i);
		for(auto& j:g[i]) {
			if(scc[i]!=scc[j]) {
				gg[scc[i]].pb(scc[j]);
			}
		}
	}
	for(i=0;i<sz(L);i++)dfs(scc[L[i].se]);
	for(i=0;i<sz(R);i++) {
		pre[i]+=vis[scc[R[i].se]];
		pre[i+1]+=pre[i];
	}
	for(i=1;i<=sc;i++) {
		for(int u:sccElem[i]) {
			if(ord[u]!=-1) {
				D[i][0]=min(D[i][0],ord[u]);
				D[i][1]=max(D[i][1],ord[u]);
			}
		}
		for(int j:gg[i]) {
			D[i][0]=min(D[i][0],D[j][0]);
			D[i][1]=max(D[i][1],D[j][1]);
		}
	}
	for(i=sz(L)-1;i>=0;i--) {
		int s=scc[L[i].se],ans;
		if(D[s][1]==-1)ans=0;
		else {
			ans=pre[D[s][1]];
			if(D[s][0])ans-=pre[D[s][0]-1];
		}
		cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:51:8: warning: unused variable 'j' [-Wunused-variable]
   51 |  int i,j;
      |        ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 14 ms 21452 KB Output is correct
3 Correct 14 ms 21412 KB Output is correct
4 Correct 14 ms 21464 KB Output is correct
5 Correct 14 ms 21452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21508 KB Output is correct
2 Correct 14 ms 21460 KB Output is correct
3 Correct 14 ms 21452 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21416 KB Output is correct
2 Correct 15 ms 21452 KB Output is correct
3 Correct 15 ms 21480 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21836 KB Output is correct
2 Correct 18 ms 22120 KB Output is correct
3 Correct 18 ms 21980 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24804 KB Output is correct
2 Correct 66 ms 28736 KB Output is correct
3 Correct 45 ms 24900 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26520 KB Output is correct
2 Correct 83 ms 30044 KB Output is correct
3 Correct 63 ms 28592 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 32388 KB Output is correct
2 Correct 149 ms 37364 KB Output is correct
3 Correct 160 ms 34296 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 32196 KB Output is correct
2 Correct 142 ms 35740 KB Output is correct
3 Correct 182 ms 34584 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 41540 KB Output is correct
2 Correct 315 ms 50752 KB Output is correct
3 Correct 394 ms 46764 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 55584 KB Output is correct
2 Correct 518 ms 64624 KB Output is correct
3 Correct 424 ms 50916 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 53892 KB Output is correct
2 Correct 551 ms 66308 KB Output is correct
3 Correct 685 ms 62120 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 52188 KB Output is correct
2 Correct 525 ms 70504 KB Output is correct
3 Correct 640 ms 61656 KB Output is correct
4 Correct 679 ms 71288 KB Output is correct