oj.uz

Submission #1110481

# Submission time Handle Problem Language Result Execution time Memory
1110481 2024-11-09T14:20:07 Z vjudge1 Traffic (CEOI11_tra) C++17
8 / 100
 879 ms 56244 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8696 KB Output is correct
3 Correct 1 ms 8528 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 11020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 15432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 21956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 23624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 32116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 434 ms 44788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 879 ms 56244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 39652 KB Output isn't correct
2 Halted 0 ms 0 KB -