| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 567242 |
2022-05-23T09:42:13 Z |
jamielim |
Jail (JOI22_jail) |
C++14 |
|
14 ms |
9288 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int q,n,m;
int fw[120005];
void upd(int x,int y){
y++;
while(y<=n){
fw[y]--;
y+=y&(-y);
}
while(x<=n){
fw[x]++;
x+=x&(-x);
}
}
int qry(int x){
int res=0;
while(x){
res+=fw[x];
x-=x&(-x);
}
return res;
}
vector<int> adj[120005];
set<int> dag[120005];
ii arr[120005];
int dep[120005];
int par[20][120005];
void dfs(int x,int p){
par[0][x]=p;
for(int i:adj[x]){
if(p==i)continue;
dep[i]=dep[x]+1;
dfs(i,x);
}
}
int lca(int x,int y){
if(x==y)return x;
if(dep[x]>dep[y])swap(x,y);
for(int i=19;i>=0;i--){
if(dep[x]<=dep[par[i][y]])y=par[i][y];
}
if(x==y)return x;
for(int i=19;i>=0;i--){
if(par[i][x]!=par[i][y])x=par[i][x],y=par[i][y];
}
return par[0][x];
}
int dist(int x,int y){
int l=lca(x,y);
int ans=0;
for(int i=19;i>=0;i--){
if(dep[par[i][x]]>=dep[l]){
x=par[i][x];
ans+=(1<<i);
}
}
for(int i=19;i>=0;i--){
if(dep[par[i][y]]>=dep[l]){
y=par[i][y];
ans+=(1<<i);
}
}
return ans;
}
vector<int> topo;
int vis[120005];
void toposort(int x){
vis[x]=1;
for(int i:dag[x]){
if(vis[i])continue;
toposort(i);
}
topo.pb(x);
}
int main(){
scanf("%d",&q);
while(q--){
scanf("%d",&n);
int a,b;
bool st1=1;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
adj[a].pb(b);adj[b].pb(a);
if(a!=i||b!=i+1)st1=0;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se);
if(st1){
bool die=0;
vector<ii> v1,v2;
for(int i=1;i<=m;i++){
if(arr[i].fi<=arr[i].se){
v1.pb(arr[i].fi,arr[i].se);
upd(arr[i].fi,arr[i].se);
}else{
v2.pb(arr[i].se,arr[i].fi);
}
}
for(int i=1;i<=m;i++){
if(arr[i].fi>arr[i].se){
if(qry(arr[i].se)){
die=1;
}
}
}
sort(ALL(v1));sort(ALL(v2));
for(int i=1;i<SZ(v1);i++){
if(v1[i].se<v1[i-1].se)die=1;
}
for(int i=1;i<SZ(v2);i++){
if(v2[i].se<v2[i-1].se)die=1;
}
if(die)printf("No\n");
else printf("Yes\n");
for(int i=0;i<=n+2;i++)fw[i]=0;
}else{
if(q<=20&&m<=500){
dfs(1,0);
dep[0]=-INF;
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
par[i][j]=par[i-1][par[i-1][j]];
}
}
int indeg[n+5];memset(indeg,0,sizeof(indeg));
set<int> ctr;
for(int i=1;i<=m;i++){
int d=dist(arr[i].fi,arr[i].se);
for(int j=1;j<=m;j++){
if(i==j)continue;
if(d==dist(arr[i].fi,arr[j].se)+dist(arr[i].se,arr[j].se)){
// j is on path of i => i is before j
dag[i].insert(j);
indeg[j]++;
ctr.insert(i);ctr.insert(j);
}
}
}
for(int i=1;i<=n;i++)if(indeg[i]==0)toposort(i);
reverse(ALL(topo));
bool die=0;
for(int i=1;i<=SZ(topo);i++){
int x=topo[i];
ctr.erase(x);
for(int j=i+1;j<=m;j++){
int y=topo[j];
if(dag[y].find(x)!=dag[y].end()){ // y is supposed to be before x
die=1;
}
}
}
if(die||SZ(ctr)!=0){
printf("No\n");
}else{
printf("Yes\n");
}
topo.clear();
memset(vis,0,sizeof(vis));
}
}
for(int i=1;i<=n;i++)adj[i].clear();
for(int i=1;i<=m;i++)dag[i].clear();
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
jail.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
jail.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
jail.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d",&m);
| ~~~~~^~~~~~~~~
jail.cpp:112:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
9024 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
8824 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
8824 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
8824 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
8824 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8788 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9288 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8820 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8660 KB |
Output is correct |
| 5 |
Incorrect |
10 ms |
8788 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8660 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
9024 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
