| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 643367 |
2022-09-21T22:18:16 Z |
Pajaraja |
Jail (JOI22_jail) |
C++17 |
|
63 ms |
110796 KB |
#include <bits/stdc++.h>
#define MAXN 120007
#define MAXL 19
using namespace std;
vector<int> g[MAXN],v[2*MAXL*MAXN];
int p[MAXL][MAXN],ind[2][MAXL][MAXN],in[MAXN],out[MAXN],t,deg[MAXN];
void dfs(int s,int f)
{
p[0][s]=f;
in[s]=++t;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
out[s]=t;
}
bool insub(int uu,int vv) {return in[uu]<=in[vv] && out[uu]>=out[vv];} //Jel v insub u
int oneunder(int uu,int vv)
{
for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv)) uu=p[i][uu];
return uu;
}
int lca(int uu,int vv)
{
if(insub(uu,vv)) return uu;
if(insub(vv,uu)) return vv;
return p[0][oneunder(uu,vv)];
}
void dostuff(int uu,int vv,int type,int br)
{
for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv))
{
if(type==0) v[br].push_back(ind[0][i][uu]);
else v[ind[1][i][uu]].push_back(br);
uu=p[i][uu];
}
if(type==0) v[br].push_back(ind[0][0][vv]);
else v[ind[1][0][vv]].push_back(br);
}
int main()
{
int q;
scanf("%d",&q);
while(q--)
{
int n,m;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int t1,t2;
scanf("%d %d",&t1,&t2);
g[t1].push_back(t2);
g[t2].push_back(t1);
}
dfs(1,1); t=0;
int c=2*n,br=0;
for(int i=1;i<=n;i++) ind[0][0][i]=i;
for(int i=1;i<=n;i++) ind[1][0][i]=n+i;
for(int j=1;j<MAXL;j++) for(int i=1;i<=n;i++)
{
p[j][i]=p[j-1][p[j-1][i]];
c++;
ind[0][j][i]=c;
v[c].push_back(ind[0][j-1][i]);
v[c].push_back(ind[0][j-1][p[j-1][i]]);
c++;
ind[1][j][i]=c;
v[ind[1][j-1][i]].push_back(c);
v[ind[1][j-1][p[j-1][i]]].push_back(c);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
c++;
int s,e;
scanf("%d%d",&s,&e);
v[s].push_back(c);
v[c].push_back(n+e);
int lc=lca(s,e);
if(lc!=s && lc!=e)
{
dostuff(p[0][s],lc,0,c);
dostuff(e,oneunder(e,lc),0,c);
dostuff(p[0][e],lc,1,c);
dostuff(s,oneunder(s,lc),1,c);
}
if(lc==s)
{
dostuff(e,oneunder(e,s),0,c);
dostuff(p[0][e],s,1,c);
}
if(lc==e)
{
dostuff(s,oneunder(s,e),1,c);
dostuff(p[0][s],e,0,c);
}
}
queue<int> q;
for(int i=1;i<=c;i++) deg[i]=0;
for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) deg[v[i][j]]++;
for(int i=1;i<=c;i++) if(deg[i]==0) q.push(i);
//for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) printf("%d %d\n",i,v[i][j]);
while(!q.empty())
{
br++;
int s=q.front(); q.pop();
for(int i=0;i<v[s].size();i++) {deg[v[s][i]]--; if(deg[v[s][i]]==0) q.push(v[s][i]);}
}
//printf("%d %d\n",c,br);
if(br==c) printf("Yes\n");
else printf("No\n");
for(int i=1;i<=c;i++) v[i].clear();
for(int i=1;i<=n;i++) g[i].clear();
}
}
Compilation message
jail.cpp: In function 'void dfs(int, int)':
jail.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
| ~^~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:97:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) deg[v[i][j]]++;
| ~^~~~~~~~~~~~
jail.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<v[s].size();i++) {deg[v[s][i]]--; if(deg[v[s][i]]==0) q.push(v[s][i]);}
| ~^~~~~~~~~~~~
jail.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
jail.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
jail.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d %d",&t1,&t2);
| ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d",&m);
| ~~~~~^~~~~~~~~
jail.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d",&s,&e);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
110384 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
110488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
110476 KB |
Output is correct |
| 2 |
Correct |
52 ms |
110376 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
110796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
110476 KB |
Output is correct |
| 2 |
Correct |
52 ms |
110376 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
110796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
110476 KB |
Output is correct |
| 2 |
Correct |
52 ms |
110376 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
110796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
110476 KB |
Output is correct |
| 2 |
Correct |
52 ms |
110376 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
110796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
110496 KB |
Output is correct |
| 2 |
Correct |
53 ms |
110468 KB |
Output is correct |
| 3 |
Incorrect |
53 ms |
110412 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
110384 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
110488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
