Submission #652653

#TimeUsernameProblemLanguageResultExecution timeMemory
652653nvujicaTraffic (CEOI11_tra)C++14
100 / 100
1628 ms91424 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int maxn = 3e5 + 10; int n, m, a, b, cur; vector <int> v[maxn]; vector <int> r[maxn]; pair<int, int> t[maxn]; int bio[maxn]; int x[maxn]; int y[maxn]; vector <int> rig; vector <int> st; int com[maxn]; vector <int> scc[maxn]; int ind[maxn]; vector <int> e[maxn]; int mn[maxn]; int mx[maxn]; int mn2[maxn]; int mx2[maxn]; vector <int> lef; void dfs1(int x){ bio[x] = 1; //cout << x << endl; for(int i = 0; i < v[x].size(); i++){ int x2 = v[x][i]; if(!bio[x2]){ dfs1(x2); } } } void dfs(int x){ bio[x] = 1; for(int i = 0; i < v[x].size(); i++){ int x2 = v[x][i]; if(!bio[x2]){ dfs(x2); } } st.push_back(x); } void dfsr(int x, int cur){ com[x] = cur; scc[cur].push_back(x); for(int i = 0; i < r[x].size(); i++){ int x2 = r[x][i]; if(!com[x2]){ dfsr(x2, cur); } } } bool cmp(int i, int j){ return y[i] > y[j]; } void rek(int x){ if(mn[x] != -1) return; mn[x] = mn2[x]; mx[x] = mx2[x]; for(int i = 0; i < e[x].size(); i++){ int x2 = e[x][i]; //if(x == 2 && x2 == 3) cout << "tu sam" << endl; rek(x2); mn[x] = min(mn[x], mn[x2]); mx[x] = max(mx[x], mx[x2]); } } int main(){ cin >> n >> m >> a >> b; for(int i = 1; i <= n; i++){ cin >> x[i] >> y[i]; } for(int i = 0; i < m; i++){ int c, d, k; cin >> c >> d >> k; v[c].push_back(d); r[d].push_back(c); if(k == 2){ v[d].push_back(c); r[c].push_back(d); } } for(int i = 1; i <= n; i++){ if(x[i] == 0 && !bio[i]){ dfs1(i); } } for(int i = 1; i <= n; i++){ if(x[i] == a && bio[i]){ rig.push_back(i); } } sort(rig.begin(), rig.end(), cmp); for(int i = 0; i < rig.size(); i++){ ind[rig[i]] = i + 1; } memset(bio, 0, sizeof bio); for(int i = 1; i <= n; i++){ if(x[i] == 0 && !bio[i]){ dfs(i); } } reverse(st.begin(), st.end()); for(int i = 0; i < st.size(); i++){ //cout << st[i] << ' '; if(!com[st[i]]){ cur++; dfsr(st[i], cur); } } //cout << endl; // for(int i = 1; i <= n; i++){ // cout << com[i] << ' '; // } for(int i = 1; i <= cur; i++){ for(int j = 0; j < scc[i].size(); j++){ int x = scc[i][j]; //cout << i << ' ' << x << endl; for(int k = 0; k < v[x].size(); k++){ int x2 = v[x][k]; if(com[x] == com[x2]) continue; //cout << "tu sam" << endl; //cout << com[x] << ' ' << com[x2] << endl; e[com[x]].push_back(com[x2]); } } } memset(mn, -1, sizeof mn); memset(mx, -1, sizeof mx); for(int i = 1; i <= cur; i++){ mn2[i] = maxn; mx2[i] = 0; } for(int i = 1; i <= n; i++){ if(x[i] == a){ mn2[com[i]] = min(mn2[com[i]], ind[i]); mx2[com[i]] = max(mx2[com[i]], ind[i]); } } for(int i = 1; i <= cur; i++){ rek(i); } // for(int i = 1; i <= cur; i++){ // cout << mn[i] << ' ' << mx[i] << endl; // } for(int i = 1; i <= n; i++){ if(x[i] == 0) lef.push_back(i); } sort(lef.begin(), lef.end(), cmp); for(int i = 0; i < lef.size(); i++){ cout << max(0, mx[com[lef[i]]] - mn[com[lef[i]]] + 1) << "\n"; } return 0; }

Compilation message (stderr)

tra.cpp: In function 'void dfs1(int)':
tra.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
tra.cpp: In function 'void dfs(int)':
tra.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
tra.cpp: In function 'void dfsr(int, int)':
tra.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < r[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
tra.cpp: In function 'void rek(int)':
tra.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < e[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
tra.cpp: In function 'int main()':
tra.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |  for(int i = 0; i < rig.size(); i++){
      |                 ~~^~~~~~~~~~~~
tra.cpp:139:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i = 0; i < st.size(); i++){
      |                 ~~^~~~~~~~~~~
tra.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   for(int j = 0; j < scc[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~
tra.cpp:157:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |    for(int k = 0; k < v[x].size(); k++){
      |                   ~~^~~~~~~~~~~~~
tra.cpp:200:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |  for(int i = 0; i < lef.size(); i++){
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...