| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 942579 |
2024-03-10T22:43:53 Z |
pcc |
Jail (JOI22_jail) |
C++17 |
|
5000 ms |
23644 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 120010;vector<int> tree[mxn];int N,M;int vcnt,ecnt;int head[mxn*100],nid[mxn*100],to[mxn*100];pii arr[mxn];const int H = 20; namespace BUILD{ int newnode(){ return ++vcnt; } void add_edge(int a,int b){ ecnt++; nid[ecnt] = head[a]; to[ecnt] = b; head[a] = ecnt; } int par[mxn][H],dep[mxn]; int stree[mxn][H],etree[mxn][H]; int sleaf[mxn],eleaf[mxn]; void dfs(int now){ sleaf[now] = newnode(); eleaf[now] = newnode(); stree[now][0] = newnode(); etree[now][0] = newnode(); add_edge(etree[now][0],eleaf[now]); add_edge(etree[now][0],eleaf[par[now][0]]); add_edge(sleaf[now],stree[now][0]); add_edge(sleaf[par[now][0]],stree[now][0]); for(int i = 1;i<H;i++){ par[now][i] = par[par[now][i-1]][i-1]; stree[now][i] = newnode(); etree[now][i] = newnode(); add_edge(stree[now][i-1],stree[now][i]); add_edge(stree[par[now][i-1]][i-1],stree[now][i]); add_edge(etree[now][i],etree[now][i-1]); add_edge(etree[now][i],etree[par[now][i-1]][i-1]); } /* cerr<<now<<":"<<sleaf[now]<<' '<<eleaf[now]<<endl;; for(int i = 0;i<H;i++)cerr<<stree[now][i]<<' ';cerr<<endl; for(int i = 0;i<H;i++)cerr<<etree[now][i]<<' ';cerr<<endl; */ for(auto nxt:tree[now]){ if(nxt == par[now][0])continue; par[nxt][0] = now; dep[nxt] = dep[now]+1; dfs(nxt); } return; } void add(int a,int b,int id){ if(dep[a]<dep[b])swap(a,b); int d = dep[a]-dep[b]; for(int i = H-1;i>=0;i--){ if(d&(1<<i)){ add_edge(stree[a][i],id); add_edge(id,etree[a][i]); a = par[a][i]; } } for(int i = H-1;i>=0;i--){ if(par[a][i] != par[b][i]){ add_edge(stree[a][i],id); add_edge(stree[b][i],id); add_edge(id,etree[a][i]); add_edge(id,etree[b][i]); a = par[a][i],b = par[b][i]; } } if(a != b){ add_edge(stree[a][0],id); add_edge(id,etree[a][0]); } return; } void GO(){ par[1][0] = 1; dfs(1); } void ADD_CON(){ for(int i = 1;i<=M;i++){ int a = arr[i].fs,b = arr[i].sc; add(a,b,i); add_edge(sleaf[a],i); add_edge(i,sleaf[a]); add_edge(eleaf[b],i); add_edge(i,eleaf[b]); /* cerr<<"ADD:"<<endl; cerr<<i<<":"<<a<<' '<<b<<' '<<sleaf[a]<<','<<eleaf[b]<<endl; */ } return; } void PRINT(){ for(int i = 1;i<=vcnt;i++){ cout<<i<<":"; for(int eid = head[i];eid;eid = nid[eid]){ cout<<to[eid]<<','; }cout<<endl; } } void init(){ dep[1] = 0; }} namespace SCC{ int deg[mxn*100],low[mxn*100],idx[mxn*100],gid[mxn*100],cnt,gcnt; int dp[mxn*100]; vector<int> st; void dfs(int now){ idx[now] = low[now] = ++cnt; st.push_back(now); for(int eid = head[now];eid;eid = nid[eid]){ int nxt = to[eid]; if(gid[nxt])continue; if(!idx[nxt]){ dfs(nxt); low[now] = min(low[now],low[nxt]); } else low[now] = min(low[now],idx[nxt]); } if(idx[now] == low[now]){ gcnt++; while(st.back() != now){ gid[st.back()] = gcnt; st.pop_back(); } gid[st.back()] = gcnt; st.pop_back(); } return; } void GO(){ for(int i = 1;i<=vcnt;i++){ if(!idx[i])dfs(i); } for(int i = 1;i<=M;i++){ dp[gid[i]]++; } if(*max_element(dp,dp+gcnt+1)>1){ cout<<"No\n"; return; } else cout<<"Yes\n"; return; } void init(){ for(int i = 1;i<=vcnt;i++){ gid[i] = dp[i] = idx[i] = low[i] = 0; } cnt=gcnt=0; return; }} void init(){ for(int i = 0;i<=N;i++){ tree[i].clear(); } SCC::init(); BUILD::init(); vcnt = ecnt = 0; return;} void solve(){ init(); cin>>N; for(int i = 1;i<N;i++){ int a,b; cin>>a>>b; tree[a].push_back(b); tree[b].push_back(a); } cin>>M; for(int i = 1;i<=M;i++){ cin>>arr[i].fs>>arr[i].sc; } vcnt = M; BUILD::GO(); BUILD::ADD_CON(); //BUILD::PRINT();
SCC::GO();} int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t;cin>>t; while(t--)solve();}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
23388 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
23484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
23388 KB |
Output is correct |
| 3 |
Execution timed out |
5061 ms |
23644 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
23388 KB |
Output is correct |
| 3 |
Execution timed out |
5061 ms |
23644 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
23388 KB |
Output is correct |
| 3 |
Execution timed out |
5061 ms |
23644 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
23388 KB |
Output is correct |
| 3 |
Execution timed out |
5061 ms |
23644 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
23644 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
23644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
23388 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
23484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
