Submission #680775

#TimeUsernameProblemLanguageResultExecution timeMemory
680775arnold518Jail (JOI22_jail)C++17
0 / 100
58 ms52084 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; int Q, N, NN, M; vector<int> adj[MAXN+10]; pii A[MAXN+10]; int idx[MAXN+10]; vector<int> adj2[MAXN*5+10]; vector<int> radj2[MAXN*5+10]; int dep[MAXN+10], par[MAXN+10], sz[MAXN+10]; void dfs(int now, int bef, int d) { dep[now]=d; par[now]=bef; sz[now]=1; for(int nxt : adj[now]) { if(nxt==bef) continue; dfs(nxt, now, d+1); sz[now]+=sz[nxt]; } } void addEdge(int u, int v) { //printf("%d %d\n", u, v); adj2[u].push_back(v); radj2[v].push_back(u); } void init(int node, int tl, int tr) { if(tl==tr) { idx[tl]=node; return; } int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); addEdge(M+node*2, M+node); addEdge(M+node*2+1, M+node); addEdge(M+N+N+node, M+N+N+node*2); addEdge(M+N+N+node, M+N+N+node*2+1); } void get(int node, int tl, int tr, int l, int r, vector<int> &V) { if(r<tl || tr<l) return; if(l<=tl && tr<=r) { V.push_back(node); return; } int mid=tl+tr>>1; get(node*2, tl, mid, l, r, V); get(node*2+1, mid+1, tr, l, r, V); } int dfn[MAXN+10], head[MAXN+10], dcnt; void hld(int now, int bef) { dfn[now]=++dcnt; int heavy=0; for(int nxt : adj[now]) if(nxt!=bef && sz[heavy]<sz[nxt]) heavy=nxt; if(!heavy) return; head[heavy]=head[now]; hld(heavy, now); for(int nxt : adj[now]) if(nxt!=bef && nxt!=heavy) { head[nxt]=nxt; hld(nxt, now); } } int vis[MAXN*5+10]; vector<int> S; void dfs2(int now) { vis[now]=1; for(int nxt : adj2[now]) if(!vis[nxt]) dfs2(nxt); S.push_back(now); } int scc[MAXN+10], scnt; void dfs3(int now) { scc[now]=scnt; for(int nxt : radj2[now]) if(!scc[nxt]) dfs3(nxt); } bool solve() { scanf("%d", &N); for(int i=1; i<N; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } scanf("%d", &M); for(int i=1; i<=M; i++) { scanf("%d%d", &A[i].first, &A[i].second); } NN=N*4+M; init(1, 1, N); dfs(1, 0, 1); head[1]=1; hld(1, 0); for(int i=1; i<=M; i++) { addEdge(i, idx[dfn[A[i].first]]+M); addEdge(idx[dfn[A[i].second]]+M+N+N, i); } for(int i=1; i<=M; i++) { int u=A[i].first, v=A[i].second; while(head[u]!=head[v]) { if(dep[u]>dep[v]) swap(u, v); vector<int> V; get(1, 1, N, dfn[head[v]], dfn[v], V); for(auto it : V) { addEdge(it+M, i); addEdge(i, it+M+N+N); } v=par[head[v]]; } if(dep[u]>dep[v]) swap(u, v); vector<int> V; get(1, 1, N, dfn[u], dfn[v], V); for(auto it : V) { addEdge(it+M, i); addEdge(i, it+M+N+N); } } for(int i=1; i<=NN; i++) if(!vis[i]) dfs2(i); reverse(S.begin(), S.end()); for(auto it : S) if(!scc[it]) scnt++, dfs3(it); set<int> SS; for(int i=1; i<=M; i++) SS.insert(scc[i]); return SS.size()==M; } void clear() { for(int i=1; i<=N; i++) { adj[i].clear(); } for(int i=1; i<=NN; i++) { adj2[i].clear(); radj2[i].clear(); vis[i]=0; scc[i]=0; } S.clear(); dcnt=0; scnt=0; } int main() { scanf("%d", &Q); while(Q--) { if(solve()) printf("Yes\n"); else printf("No\n"); clear(); } }

Compilation message (stderr)

jail.cpp: In function 'void init(int, int, int)':
jail.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=tl+tr>>1;
      |          ~~^~~
jail.cpp: In function 'void get(int, int, int, int, int, std::vector<int>&)':
jail.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid=tl+tr>>1;
      |          ~~^~~
jail.cpp: In function 'bool solve()':
jail.cpp:166:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  166 |  return SS.size()==M;
      |         ~~~~~~~~~^~~
jail.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
jail.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
jail.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:189:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
#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...