| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 815128 |
2023-08-08T12:34:53 Z |
jajco |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
212 KB |
#include <ios>
#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);
}
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){
int cp=-1,ck=-1;
czy=1;
for (int i=1; i<=n; ++i){
if (pn[i]>=0){
if (ck==pn[i])
ck=-1;
if (cp>=0||ck>=0){
czy=0;
goto fin;}
}
if (kn[i]>=0){
if (cp==kn[i])
cp=-1;
if (cp>=0||ck>=0){
czy=0;
goto fin;
}
}
}
goto fin;
}
REP(k, m){ // generacja daga
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){
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]];
}
return r;
};
DFS(pocz[k], pocz[k], kon[k], k);
}
{
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:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
jail.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
jail.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d%d", &p, &k);
| ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
jail.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%d%d", &pocz[i], &kon[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
