답안 #670341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670341	2022-12-08T17:16:52 Z	MilosMilutinovic	Jail (JOI22_jail)	C++14	49 / 100	5000 ms	39352 KB

jail

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#define pb push_back
#define mk make_pair
using namespace std;
int n,m,go[120005][22],dep[120005],s[505],t[505],dfn[120005],dfo[120005],T;
vector<int> g[120005];
void dfs(int v,int pr)
{
	dep[v]=dep[pr]+1;go[v][0]=pr;dfn[v]=++T;
	for(int u:g[v])if(u!=pr)dfs(u,v);
	dfo[v]=T;
}
bool in(int x,int y){return dfn[x]<=dfn[y]&&dfo[y]<=dfo[x];}
int lca(int u,int v)
{
	int x=u;while(!in(x,v))x=go[x][0];return x;
	/*if(dep[u]<dep[v])swap(u,v);
	for(int i=19;i>=0;i--)if(dep[go[u][i]]>=dep[v])u=go[u][i];
	assert(u!=0);
	if(u==v)return u;
	assert(dep[u]==dep[v]);
	for(int i=19;i>=0;i--)if(go[u][i]!=go[v][i])u=go[u][i],v=go[v][i];
	assert(go[u][0]!=0);
	return go[u][0];*/
}
int deg[505];vector<int> e[505];
void init()
{
	T=0;
	for(int i=1;i<=120000;i++)g[i].clear(),dep[i]=0;
	for(int i=1;i<=120000;i++)for(int j=0;j<20;j++)go[i][j]=0;
	for(int i=1;i<=500;i++)deg[i]=0,e[i].clear();
}
void adde(int x,int y){deg[y]++;e[x].pb(y);}
bool on(int x,int y,int z){int l=lca(x,y);return in(l,z)&&(in(z,x)||in(z,y));}
int qu[505],qsz;
void solve()
{
	init();scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
	dfs(1,0);
	for(int j=1;j<20;j++)for(int i=1;i<=n;i++)go[i][j]=go[go[i][j-1]][j-1];
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&s[i],&t[i]);
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(i!=j&&on(s[i],t[i],s[j]))adde(j,i);
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(i!=j&&on(s[i],t[i],t[j]))adde(i,j);
	qsz=0;for(int i=1;i<=m;i++)if(deg[i]==0)qu[++qsz]=i;
	for(int i=1;i<=qsz;i++)for(int j:e[qu[i]]){
		deg[j]--;
		if(deg[j]==0)qu[++qsz]=j;
		assert(deg[j]>=0);
	}
	bool ok=1;for(int i=1;i<=m;i++)ok&=(deg[i]==0);
	printf(ok?"Yes\n":"No\n");
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)solve();
	return 0;
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  init();scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:54:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
      |                          ~~~~~^~~~~~~~~~~~~~
jail.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d",&m);
      |  ~~~~~^~~~~~~~~
jail.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  for(int i=1;i<=m;i++)scanf("%d%d",&s[i],&t[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:72:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  int t;scanf("%d",&t);
      |        ~~~~~^~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	13908 KB	Output is correct
2	Correct	9 ms	13952 KB	Output is correct
3	Correct	6 ms	13952 KB	Output is correct
4	Correct	616 ms	13956 KB	Output is correct
5	Correct	1317 ms	14688 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	32 ms	13984 KB	Output is correct
8	Correct	56 ms	14028 KB	Output is correct
9	Execution timed out	5060 ms	16812 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	13908 KB	Output is correct
2	Correct	6 ms	13908 KB	Output is correct
3	Correct	33 ms	13928 KB	Output is correct
4	Correct	34 ms	13908 KB	Output is correct
5	Correct	33 ms	13980 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	33 ms	14028 KB	Output is correct
8	Correct	38 ms	13980 KB	Output is correct
9	Correct	34 ms	14104 KB	Output is correct
10	Correct	33 ms	13908 KB	Output is correct
11	Correct	28 ms	13908 KB	Output is correct
12	Correct	32 ms	13908 KB	Output is correct
13	Correct	32 ms	13912 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	13908 KB	Output is correct
2	Correct	6 ms	13908 KB	Output is correct
3	Correct	33 ms	13928 KB	Output is correct
4	Correct	34 ms	13908 KB	Output is correct
5	Correct	33 ms	13980 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	33 ms	14028 KB	Output is correct
8	Correct	38 ms	13980 KB	Output is correct
9	Correct	34 ms	14104 KB	Output is correct
10	Correct	33 ms	13908 KB	Output is correct
11	Correct	28 ms	13908 KB	Output is correct
12	Correct	32 ms	13908 KB	Output is correct
13	Correct	32 ms	13912 KB	Output is correct
14	Correct	9 ms	13908 KB	Output is correct
15	Correct	9 ms	13896 KB	Output is correct
16	Correct	33 ms	13908 KB	Output is correct
17	Correct	38 ms	13980 KB	Output is correct
18	Correct	34 ms	13908 KB	Output is correct
19	Correct	31 ms	13908 KB	Output is correct
20	Correct	33 ms	13908 KB	Output is correct
21	Correct	33 ms	13980 KB	Output is correct
22	Correct	33 ms	13992 KB	Output is correct
23	Correct	35 ms	13908 KB	Output is correct
24	Correct	32 ms	13908 KB	Output is correct
25	Correct	33 ms	13908 KB	Output is correct
26	Correct	33 ms	13908 KB	Output is correct
27	Correct	33 ms	13992 KB	Output is correct
28	Correct	31 ms	13908 KB	Output is correct

Subtask #4
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	13908 KB	Output is correct
2	Correct	6 ms	13908 KB	Output is correct
3	Correct	33 ms	13928 KB	Output is correct
4	Correct	34 ms	13908 KB	Output is correct
5	Correct	33 ms	13980 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	33 ms	14028 KB	Output is correct
8	Correct	38 ms	13980 KB	Output is correct
9	Correct	34 ms	14104 KB	Output is correct
10	Correct	33 ms	13908 KB	Output is correct
11	Correct	28 ms	13908 KB	Output is correct
12	Correct	32 ms	13908 KB	Output is correct
13	Correct	32 ms	13912 KB	Output is correct
14	Correct	9 ms	13908 KB	Output is correct
15	Correct	9 ms	13896 KB	Output is correct
16	Correct	33 ms	13908 KB	Output is correct
17	Correct	38 ms	13980 KB	Output is correct
18	Correct	34 ms	13908 KB	Output is correct
19	Correct	31 ms	13908 KB	Output is correct
20	Correct	33 ms	13908 KB	Output is correct
21	Correct	33 ms	13980 KB	Output is correct
22	Correct	33 ms	13992 KB	Output is correct
23	Correct	35 ms	13908 KB	Output is correct
24	Correct	32 ms	13908 KB	Output is correct
25	Correct	33 ms	13908 KB	Output is correct
26	Correct	33 ms	13908 KB	Output is correct
27	Correct	33 ms	13992 KB	Output is correct
28	Correct	31 ms	13908 KB	Output is correct
29	Correct	52 ms	14016 KB	Output is correct
30	Correct	35 ms	13908 KB	Output is correct
31	Correct	44 ms	14016 KB	Output is correct
32	Correct	38 ms	13908 KB	Output is correct
33	Correct	33 ms	13988 KB	Output is correct
34	Correct	38 ms	14016 KB	Output is correct
35	Correct	74 ms	14004 KB	Output is correct
36	Correct	37 ms	13908 KB	Output is correct
37	Correct	40 ms	13908 KB	Output is correct

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	13908 KB	Output is correct
2	Correct	6 ms	13908 KB	Output is correct
3	Correct	33 ms	13928 KB	Output is correct
4	Correct	34 ms	13908 KB	Output is correct
5	Correct	33 ms	13980 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	33 ms	14028 KB	Output is correct
8	Correct	38 ms	13980 KB	Output is correct
9	Correct	34 ms	14104 KB	Output is correct
10	Correct	33 ms	13908 KB	Output is correct
11	Correct	28 ms	13908 KB	Output is correct
12	Correct	32 ms	13908 KB	Output is correct
13	Correct	32 ms	13912 KB	Output is correct
14	Correct	9 ms	13908 KB	Output is correct
15	Correct	9 ms	13896 KB	Output is correct
16	Correct	33 ms	13908 KB	Output is correct
17	Correct	38 ms	13980 KB	Output is correct
18	Correct	34 ms	13908 KB	Output is correct
19	Correct	31 ms	13908 KB	Output is correct
20	Correct	33 ms	13908 KB	Output is correct
21	Correct	33 ms	13980 KB	Output is correct
22	Correct	33 ms	13992 KB	Output is correct
23	Correct	35 ms	13908 KB	Output is correct
24	Correct	32 ms	13908 KB	Output is correct
25	Correct	33 ms	13908 KB	Output is correct
26	Correct	33 ms	13908 KB	Output is correct
27	Correct	33 ms	13992 KB	Output is correct
28	Correct	31 ms	13908 KB	Output is correct
29	Correct	52 ms	14016 KB	Output is correct
30	Correct	35 ms	13908 KB	Output is correct
31	Correct	44 ms	14016 KB	Output is correct
32	Correct	38 ms	13908 KB	Output is correct
33	Correct	33 ms	13988 KB	Output is correct
34	Correct	38 ms	14016 KB	Output is correct
35	Correct	74 ms	14004 KB	Output is correct
36	Correct	37 ms	13908 KB	Output is correct
37	Correct	40 ms	13908 KB	Output is correct
38	Execution timed out	5082 ms	16852 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	13952 KB	Output is correct
2	Correct	8 ms	13952 KB	Output is correct
3	Correct	9 ms	13908 KB	Output is correct
4	Correct	6 ms	13908 KB	Output is correct
5	Correct	1356 ms	14068 KB	Output is correct
6	Correct	32 ms	13908 KB	Output is correct
7	Correct	36 ms	13904 KB	Output is correct
8	Correct	34 ms	13896 KB	Output is correct
9	Correct	32 ms	13908 KB	Output is correct
10	Correct	32 ms	13888 KB	Output is correct
11	Correct	31 ms	13904 KB	Output is correct
12	Correct	38 ms	14000 KB	Output is correct
13	Correct	1412 ms	14652 KB	Output is correct
14	Correct	1363 ms	14812 KB	Output is correct
15	Correct	1368 ms	14704 KB	Output is correct
16	Runtime error	138 ms	39352 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	13908 KB	Output is correct
2	Correct	9 ms	13952 KB	Output is correct
3	Correct	6 ms	13952 KB	Output is correct
4	Correct	616 ms	13956 KB	Output is correct
5	Correct	1317 ms	14688 KB	Output is correct
6	Correct	33 ms	13908 KB	Output is correct
7	Correct	32 ms	13984 KB	Output is correct
8	Correct	56 ms	14028 KB	Output is correct
9	Execution timed out	5060 ms	16812 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

답안 #670341

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 28.0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
16.0 / 16.0

Subtask #4
28.0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0