Submission #1110481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110481		vjudge1	Traffic (CEOI11_tra)	C++17	8 / 100	879 ms	56244 KiB

tra

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 1e6 + 5;
const int mod = 1e9 + 7;
using namespace std;
pii a[mxN];
set<pii>s,e;
vector<vector<int>>v,v1;
bool vis[mxN];
int id[mxN];
int l[mxN],r[mxN];
int mx;
int mn;
int sz;
int ans[mxN];
void dfs(int u){
  mx = max(mx,id[u]);
  if(id[u]) mn = min(mn,id[u]);
  vis[u] = 1;
  for(auto x : v[u]){
    if(vis[x]) continue;
    dfs(x);
  }
}
void dfs1(int u){
  vis[u] = 1;
  for(auto x : v1[u]){
    if(vis[x]) continue;
    dfs1(x);
  }
}
signed main(){
  // ios_base::sync_with_stdio(0);
  // cin.tie(0);
  // cout.tie(0);
  int n,m,A,B;
  cin >>n>>m>>A>>B;
  vector<pii>og;
  for(int i = 1;i <= n;i++){
    cin>>a[i].F>>a[i].S;
    if(a[i].F == 0) {
      s.insert({a[i].S,i});
      og.push_back({a[i].S,i});
    }
    if(a[i].F == A) e.insert({a[i].S,i});
  }
  sort(og.begin(),og.end());
  reverse(og.begin(),og.end());
  sz = s.size();
  v.resize(n + 4);
  v1.resize(n + 4);
  for(int i = 1;i <= m;i++){
    int x,y,t;
    cin >>x>>y>>t;
    v[x].push_back(y);
    v1[y].push_back(x);
    if(t == 2) v[y].push_back(x);
    if(t == 2) v1[x].push_back(y);
  }
  queue<pii>rem;
  for(auto x : s){
    dfs(x.S);
  }
  for(auto x : e){
    if(!vis[x.S]) rem.push(x);
  }
  while(rem.size()){
    e.erase(rem.front());
    rem.pop();
  }
  memset(vis,0,sizeof vis);
  for(auto x : e){
    dfs1(x.S);
  }
  for(auto x : s){
    if(!vis[x.S]) rem.push(x);
  }
  while(rem.size()){
    s.erase(rem.front());
    rem.pop();
  }
  memset(vis,0,sizeof vis);
  int ids = 1;
  for(auto x : e) id[x.S] = ids++;
  vector<pii>temp;
  for(auto x : s){
    mx = 0;
    // cout<<x.S<<' ';
    dfs(x.S);
    if(mx == 0) mx = e.size();
    r[x.S] = mx;
    temp.push_back(x);
  }
  // cout<<'\n';
  memset(vis,0,sizeof vis);
  reverse(temp.begin(),temp.end());
  for(auto x : temp){
    mn = 1e9;
    dfs(x.S);
    if(mn == 1e9) mn = 1;
    l[x.S] = mn;
    ans[x.S] = r[x.S] - l[x.S] + 1;
  }
  for(auto x : og){
    cout<<ans[x.S]<<'\n';
  }

}

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