Submission #392719

#	Time	Username	Problem	Language	Result	Execution time	Memory
392719		junodeveloper	Traffic (CEOI11_tra)	C++17	100 / 100	685 ms	71288 KiB

tra

#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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9