제출 #567216

#제출 시각아이디문제언어결과실행 시간메모리
567216dantoh000Jail (JOI22_jail)C++14
61 / 100
2266 ms27716 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; int q; int n,m; int s[120005], t[120005]; int p[120005][18]; int d[120005]; vector<int> G2[120005]; vector<int> G[120005]; int vis[120005]; vector<ii> K; int lca(int x, int y){ ///printf("LCA %d %d\n",x,y); if (d[x] > d[y]) swap(x,y); int diff = d[y]-d[x]; for (int k = 0; k < 18; k++){ if (diff>>k&1) { y = p[y][k]; } } if (x == y) return x; for (int k = 17; k >= 0; k--){ if (p[x][k] && p[y][k] && p[x][k] != p[y][k]){ x = p[x][k]; y = p[y][k]; } } assert(p[x][0] == p[y][0]); return p[x][0]; } void dfs(int u, int p_){ p[u][0] = p_; for (auto v: G[u]){ if (v == p_) continue; d[v] = d[u]+1; dfs(v,u); } } bool check(int x, int y, int z){ int r = lca(x,y); return (lca(r,z) == r) && (lca(x,z) == z || lca(y,z) == z); } bool dfs2(int u){ vis[u] = 2; bool can = true; for (auto v : G2[u]){ if (vis[v] == 2) return false; else if (vis[v] == 0){ can &= dfs2(v); }; } vis[u] = 1; return can; } int main(){ scanf("%d",&q); while (q--){ scanf("%d",&n); for (int i = 1; i <= n; i++) G[i].clear(); for (int i = 1,a,b; i < n; i++){ scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } scanf("%d",&m); for (int i = 0; i < m; i++){ scanf("%d%d",&s[i],&t[i]); } if (m <= 500 && q <= 20){ d[1] = 0; dfs(1,0); for (int k = 1; k < 18; k++){ for (int i = 1; i <= n; i++){ p[i][k] = p[p[i][k-1]][k-1]; } } for (int i = 0; i < m; i++) G2[i].clear(); for (int i = 0; i < m; i++){ for (int j = 0; j < m; j++){ if (i == j) continue; if (check(s[i], t[i], s[j])){ ///printf("%d before %d\n",j,i); G2[i].push_back(j); } if (check(s[i], t[i], t[j])){ ///printf("%d before %d\n",i,j); G2[j].push_back(i); } } } bool can = true; fill(vis,vis+m, 0); for (int i = 0; i < m; i++){ if (vis[i] == 0){ can &= dfs2(i); } } printf("%s\n",can?"Yes":"No"); } else{ K.clear(); for (int i = 0; i < n; i++){ K.push_back({s[i],t[i]}); } sort(K.begin(),K.end()); bool can = true; for (int i = 1; i < n; i++){ if (K[i].second < K[i-1].second) can = false; } printf("%s\n",can?"Yes":"No"); } } }

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

jail.cpp: In function 'int main()':
jail.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
jail.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
jail.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |             scanf("%d%d",&s[i],&t[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...