제출 #117360

#제출 시각아이디문제언어결과실행 시간메모리
117360imyujinTraffic (CEOI11_tra)C++14
0 / 100
1177 ms48908 KiB
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; #define MAXN 300005 #define MAXM 900005 int x[MAXN], y[MAXN]; int c[MAXM], d[MAXM], k[MAXM]; vector<int> e[MAXN], einv[MAXN]; int l[MAXN], r[MAXN], ln, rn; bool ava[MAXN]; int mn[MAXN], mx[MAXN]; int chk[MAXN]; bool cmp(int a, int b){ return y[a]<y[b]; } void dfs(int p, int q){ //printf("[%d %d]\n", p, q); chk[p]=q; for(auto a:e[p]) if(chk[a]==-1) dfs(a, q); } void dfsinv(int p){ chk[p]=0; for(auto a:einv[p]) if(chk[a]==-1) dfsinv(a); } int main(){ int n, m, A, B; scanf("%d%d%d%d", &n, &m, &A, &B); for(int i=1; i<=n; i++) scanf("%d%d", x+i, y+i); for(int i=0; i<m; i++) scanf("%d%d%d", c+i, d+i, k+i); for(int i=0; i<m; i++){ e[c[i]].push_back(d[i]); einv[d[i]].push_back(c[i]); if(k[i]==2){ e[d[i]].push_back(c[i]); einv[c[i]].push_back(d[i]); } } for(int i=1; i<=n; i++) if(x[i]==0) l[ln++]=i; sort(l, l+ln, cmp); for(int i=1; i<=n; i++) chk[i]=-1; for(int i=1; i<=n; i++) if(x[i]==A) dfsinv(i); for(int i=0; i<ln; i++) ava[i]=chk[l[i]]!=-1; for(int i=1; i<=n; i++) chk[i]=-1; for(int i=0; i<ln; i++) if(ava[i]&&chk[l[i]]==-1) dfs(l[i], i); for(int i=1; i<=n; i++) if(x[i]==A&&chk[i]!=-1) r[rn++]=i; sort(r, r+rn, cmp); for(int i=0; i<ln; i++){ mn[i]=rn-1; mx[i]=0; } //for(int i=1; i<=n; i++) printf("%d*\n", chk[i]); //for(int i=0; i<rn; i++) printf("*%d", r[i]); for(int i=0; i<rn; i++) mx[chk[r[i]]]=i; //for(int i=0; i<ln; i++) printf("(%d)\n", mx[i]); for(int i=1; i<ln; i++) if(mx[i-1]>mx[i]) mx[i]=mx[i-1]; for(int i=1; i<=n; i++) chk[i]=-1; for(int i=ln-1; i>=0; i--) dfs(l[i], i); for(int i=rn-1; i>=0; i--) mn[chk[r[i]]]=i; for(int i=ln-2; i>=0; i--) if(mn[i+1]<mn[i]) mn[i]=mn[i+1]; for(int i=0; i<ln; i++) printf("[%d %d]\n", mn[i], mx[i]); for(int i=ln-1; i>=0; i--) printf("%d\n", ava[i]?mx[i]-mn[i]+1:0); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

tra.cpp: In function 'int main()':
tra.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
                          ~~~~~^~~~~~~~~~~~~~~~~~
tra.cpp:38:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<m; i++) scanf("%d%d%d", c+i, d+i, k+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...