oj.uz

Submission #1110482

# Submission time Handle Problem Language Result Execution time Memory
1110482 2024-11-09T14:26:05 Z vjudge1 Traffic (CEOI11_tra) C++17
100 / 100
 897 ms 69228 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;
  int prev;
  for(auto x : s){
    mx = 0;
    // cout<<x.S<<' ';
    dfs(x.S);
    if(mx == 0) mx = r[prev];
    r[x.S] = mx;
    temp.push_back(x);
    prev = x.S;
  }
  // 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 = l[prev];
    l[x.S] = mn;
    ans[x.S] = r[x.S] - l[x.S] + 1;
    prev = x.S;
  }
  for(auto x : og){
    cout<<ans[x.S]<<'\n';
  }

}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:105:30: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |     if(mn == 1e9) mn = l[prev];
      |                        ~~~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8784 KB Output is correct
2 Correct 7 ms 9468 KB Output is correct
3 Correct 8 ms 9040 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11088 KB Output is correct
2 Correct 72 ms 18600 KB Output is correct
3 Correct 41 ms 11440 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15468 KB Output is correct
2 Correct 90 ms 20164 KB Output is correct
3 Correct 53 ms 16200 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21892 KB Output is correct
2 Correct 133 ms 27172 KB Output is correct
3 Correct 181 ms 24272 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 23564 KB Output is correct
2 Correct 149 ms 27780 KB Output is correct
3 Correct 198 ms 24656 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 32272 KB Output is correct
2 Correct 339 ms 42048 KB Output is correct
3 Correct 407 ms 36164 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 44860 KB Output is correct
2 Correct 531 ms 62360 KB Output is correct
3 Correct 430 ms 39404 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 56372 KB Output is correct
2 Correct 602 ms 62172 KB Output is correct
3 Correct 765 ms 51784 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 39752 KB Output is correct
2 Correct 581 ms 60060 KB Output is correct
3 Correct 781 ms 49368 KB Output is correct
4 Correct 897 ms 69228 KB Output is correct