| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876792 |
2023-11-22T10:43:12 Z |
vivkostov |
Jail (JOI22_jail) |
C++14 |
|
3 ms |
19036 KB |
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int q,n,m,c,d,a[200005],b[200005],tip[200005],up[200005],lev[200005],bin[200005][30],whos[200005],whof[200005],marked[505][505],usedc[200005];
vector<int>v[200005],mod[200005];
void dfs(int beg,int last,int level,int p)
{
lev[beg]=level;
bin[beg][0]=p;
int w;
if(tip[beg])
{
up[beg]=last;
last=beg;
}
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!lev[w])dfs(w,last,level+1,beg);
}
}
void make_bin()
{
for(int i=1;i<=n;i++)
{
int j=1;
while(bin[bin[i][j-1]][j-1]!=0)
{
bin[i][j]=bin[bin[i][j-1]][j-1];
j++;;
}
}
}
int lca(int a,int b)
{
if(lev[a]>lev[b])swap(a,b);
for(int i=29;i>=0;i--)
{
if(lev[a]<=lev[bin[b][i]])b=bin[b][i];
}
if(a==b)return a;
for(int i=29;i>=0;i--)
{
if(bin[a][i]!=bin[b][i])
{
a=bin[a][i];
b=bin[b][i];
}
}
return bin[a][0];
}
void make_graph(int g)
{
int l=lev[lca(a[g],b[g])],seg=up[a[g]];
while(lev[seg]>=l)
{
if(tip[seg]==1&&!marked[whos[seg]][g])
{
mod[whos[seg]].push_back(g);
marked[whos[seg]][g]=1;
}
if(tip[seg]==2&&!marked[g][whof[seg]])
{
mod[g].push_back(whof[seg]);
marked[g][whof[seg]]=1;
}
seg=up[seg];
}
seg=up[b[g]];
while(lev[seg]>=l)
{
if(tip[seg]==1&&!marked[whos[seg]][g])
{
mod[whos[seg]].push_back(g);
marked[whos[seg]][g]=1;
}
if(tip[seg]==2&&!marked[g][whof[seg]])
{
mod[g].push_back(whof[seg]);
marked[g][whof[seg]]=1;
}
seg=up[seg];
}
}
int lamp;
void cycle(int beg,int par)
{
int w;
usedc[beg]=1;
for(int i=0;i<mod[beg].size();i++)
{
w=mod[beg][i];
if(!usedc[w])cycle(w,beg);
if(usedc[w]==1&&w!=beg)
{
lamp=1;
return;
}
}
usedc[beg]=2;
}
void resh()
{
dfs(1,0,1,0);
make_bin();
for(int i=1;i<=m;i++)make_graph(i);
for(int i=1;i<=m;i++)
{
//cout<<i<<" | ";
for(int j=0;j<mod[i].size();j++)
{
//cout<<mod[i][j]<<" ";
}
//cout<<endl;
}
for(int i=1;i<=m;i++)
{
if(!usedc[i])cycle(i,0);
}
if(lamp)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
for(int i=1;i<=n;i++)
{
tip[i]=0;
up[i]=0;
lev[i]=0;
for(int j=0;j<=29;j++)bin[i][j]=0;
whos[i]=0;
whof[i]=0;
usedc[i]=0;
v[i].clear();
mod[i].clear();
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
marked[i][j]=0;
}
}
lamp=0;
}
void read()
{
cin>>q;
for(int z=1;z<=q;z++)
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>c>>d;
v[c].push_back(d);
v[d].push_back(c);
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
whos[a[i]]=i;
whof[b[i]]=i;
tip[a[i]]=1;
tip[b[i]]=2;
}
resh();
}
}
int main()
{
speed();
read();
return 0;
}
Compilation message
jail.cpp: In function 'void dfs(int, int, int, int)':
jail.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
jail.cpp: In function 'void cycle(int, int)':
jail.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0;i<mod[beg].size();i++)
| ~^~~~~~~~~~~~~~~~
jail.cpp: In function 'void resh()':
jail.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=0;j<mod[i].size();j++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
