| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 815176 |
2023-08-08T12:56:25 Z |
jajco |
Jail (JOI22_jail) |
C++17 |
|
13 ms |
648 KB |
#include <ios>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#define REP(i, n) for (int i=0; i<n; ++i)
typedef std::vector <int> vi;
int main(){
int q;
scanf("%d", &q);
while (q--){
int n;
scanf("%d", &n);
std::vector <vi> pol(n+1, vi());
bool liniow=1;
REP(i, n-1){ // wczytanie grafu
int p,k;
scanf("%d%d", &p, &k);
if (p!=k-1)
liniow=0;
pol[p].emplace_back(k);
pol[k].emplace_back(p);
}
vi gl(n+1),ojc(n+1);
{ // glebokosci
std::function <void(int, int, int)> DFS=[&](
int i, int o, int g){
ojc[i]=o;
gl[i]=g;
for (int j : pol[i])
if (j!=o)
DFS(j, i, g+1);
};
DFS(1, 0, 1);
}
int m;
scanf("%d", &m);
vi pocz(m),kon(m),perm,pn(n+1, -1),kn(n+1, -1);
REP(i, m){ // wczytanie ziomow
scanf("%d%d", &pocz[i], &kon[i]);
pn[pocz[i]]=i,kn[kon[i]]=i;
}
std::vector <vi> dag(m, vi());
vi ile(m);
bool czy;
if (liniow){
std::set <int> v,rv;
czy=1;
REP(i, m){
if (pocz[i]<kon[i]){
v.insert(pocz[i]);
v.insert(kon[i]);
}
else{
rv.insert(pocz[i]);
rv.insert(kon[i]);
}
}
REP(i, m){
if (pocz[i]<kon[i]){
auto itr=rv.lower_bound(pocz[i]);
if (itr!=rv.end()&&*itr<=kon[i])
czy=0;
}
else{
auto itr=v.lower_bound(pocz[i]);
if (itr!=v.end()&&*itr<=kon[i])
czy=0;
}
}
goto fin;
}
{
auto mkkraw=[&](int i, int id){
if (pn[i]>=0&&pn[i]!=id) // musimy byc po nim
dag[pn[i]].emplace_back(id),++ile[id];
if (kn[i]>=0&&kn[i]!=id) // musimy byc przed nim
dag[id].emplace_back(kn[i]),++ile[kn[i]];
};
if (m<=500)
REP(k, m){ // generacja daga dfsami
static std::function <
bool(int, int, int, int)> DFS=[&](
int i, int ojc, int d, int id){
bool r=i==d;
if (!r)
for (int j : pol[i])
if (j!=ojc)
if (r|=DFS(j, i, d, id))
break;
if (r)
mkkraw(i, id);
return r;
};
DFS(pocz[k], pocz[k], kon[k], k);
}
else{
REP(i, m){ // generacja daga idac w gore do LCA
int p=pocz[i],k=kon[i];
if (gl[p]>gl[k])
std::swap(p, k);
while (p!=k){ // p ma mniejsze gl
if (gl[p]==gl[k])
mkkraw(p, i),p=ojc[p];
else
mkkraw(k, i),k=ojc[k];
}
mkkraw(p, i);
}
}
{ // check daga
vi zer;
REP(i, m)
if (!ile[i])
zer.emplace_back(i);
int w=0;
while (zer.size()){
++w;
int p=zer.back();
zer.pop_back();
for (int i : dag[p])
if (!--ile[i])
zer.emplace_back(i);
}
czy=w==m;
}
}
fin:
printf(czy ? "Yes\n" : "No\n");
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
jail.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
jail.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d%d", &p, &k);
| ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
jail.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d", &pocz[i], &kon[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
648 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
288 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
648 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
