oj.uz

Submission #680779

# Submission time Handle Problem Language Result Execution time Memory
680779 2023-01-11T19:03:59 Z arnold518 Jail (JOI22_jail) C++17
5 / 100
 1181 ms 216788 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int Q, N, NN, M;
vector<int> adj[MAXN+10];
pii A[MAXN+10];
int idx[MAXN+10];

vector<int> adj2[MAXN*10+10];
vector<int> radj2[MAXN*10+10];

int dep[MAXN+10], par[MAXN+10], sz[MAXN+10];
void dfs(int now, int bef, int d)
{
	dep[now]=d;
	par[now]=bef;
	sz[now]=1;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		sz[now]+=sz[nxt];
	}
}

void addEdge(int u, int v)
{
	//printf("%d %d\n", u, v);
	adj2[u].push_back(v);
	radj2[v].push_back(u);
}

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		idx[tl]=node;
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);

	addEdge(M+node*2, M+node);
	addEdge(M+node*2+1, M+node);
	addEdge(M+N*4+node, M+N*4+node*2);
	addEdge(M+N*4+node, M+N*4+node*2+1);
}

void get(int node, int tl, int tr, int l, int r, vector<int> &V)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		V.push_back(node);
		return;
	}
	int mid=tl+tr>>1;
	get(node*2, tl, mid, l, r, V);
	get(node*2+1, mid+1, tr, l, r, V);
}

int dfn[MAXN+10], head[MAXN+10], dcnt;
void hld(int now, int bef)
{
	dfn[now]=++dcnt;

	int heavy=0;
	for(int nxt : adj[now]) if(nxt!=bef && sz[heavy]<sz[nxt]) heavy=nxt;
	if(!heavy) return;

	head[heavy]=head[now];
	hld(heavy, now);

	for(int nxt : adj[now]) if(nxt!=bef && nxt!=heavy)
	{
		head[nxt]=nxt;
		hld(nxt, now);
	}
}

int vis[MAXN*10+10];
vector<int> S;
void dfs2(int now)
{
	vis[now]=1;
	for(int nxt : adj2[now]) if(!vis[nxt]) dfs2(nxt);
	S.push_back(now);
}

int scc[MAXN*10+10], scnt;
void dfs3(int now)
{
	scc[now]=scnt;
	for(int nxt : radj2[now]) if(!scc[nxt]) dfs3(nxt);
}

bool solve()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	scanf("%d", &M);
	for(int i=1; i<=M; i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
	}

	NN=N*8+M;

	init(1, 1, N);
	dfs(1, 0, 1);

	head[1]=1;
	hld(1, 0);

	for(int i=1; i<=M; i++)
	{
		addEdge(i, idx[dfn[A[i].first]]+M);
		addEdge(idx[dfn[A[i].second]]+M+N*4, i);
	}

	for(int i=1; i<=M; i++)
	{
		int u=A[i].first, v=A[i].second;
		while(head[u]!=head[v])
		{
			if(dep[u]>dep[v]) swap(u, v);

			vector<int> V;
			get(1, 1, N, dfn[head[v]], dfn[v], V);
			for(auto it : V)
			{
				addEdge(it+M, i);
				addEdge(i, it+M+N*4);
			}
			v=par[head[v]];
		}
		if(dep[u]>dep[v]) swap(u, v);
		vector<int> V;
		get(1, 1, N, dfn[u], dfn[v], V);
		for(auto it : V)
		{
			addEdge(it+M, i);
			addEdge(i, it+M+N*4);
		}
	}

	for(int i=1; i<=NN; i++) if(!vis[i]) dfs2(i);
	reverse(S.begin(), S.end());
	for(auto it : S) if(!scc[it]) scnt++, dfs3(it);

	set<int> SS;
	for(int i=1; i<=M; i++) SS.insert(scc[i]);
	return SS.size()==M;
}

void clear()
{
	for(int i=1; i<=N; i++)
	{
		adj[i].clear();
	}
	for(int i=1; i<=NN; i++)
	{
		adj2[i].clear();
		radj2[i].clear();
		vis[i]=0;
		scc[i]=0;
	}
	S.clear();
	dcnt=0;
	scnt=0;
}

int main()
{
	scanf("%d", &Q);
	while(Q--)
	{
		if(solve()) printf("Yes\n");
		else printf("No\n");
		clear();
	}
}

Compilation message

jail.cpp: In function 'void init(int, int, int)':
jail.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=tl+tr>>1;
      |          ~~^~~
jail.cpp: In function 'void get(int, int, int, int, int, std::vector<int>&)':
jail.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid=tl+tr>>1;
      |          ~~^~~
jail.cpp: In function 'bool solve()':
jail.cpp:166:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  166 |  return SS.size()==M;
      |         ~~~~~~~~~^~~
jail.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
jail.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
jail.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:189:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98892 KB Output is correct
2 Correct 50 ms 98928 KB Output is correct
3 Correct 53 ms 98900 KB Output is correct
4 Correct 71 ms 99032 KB Output is correct
5 Correct 100 ms 99544 KB Output is correct
6 Correct 52 ms 99116 KB Output is correct
7 Correct 52 ms 99028 KB Output is correct
8 Correct 58 ms 99176 KB Output is correct
9 Correct 117 ms 102416 KB Output is correct
10 Correct 211 ms 149684 KB Output is correct
11 Correct 71 ms 99128 KB Output is correct
12 Correct 120 ms 99712 KB Output is correct
13 Correct 362 ms 164872 KB Output is correct
14 Correct 415 ms 163024 KB Output is correct
15 Correct 695 ms 173420 KB Output is correct
16 Correct 1181 ms 216788 KB Output is correct
17 Correct 464 ms 182964 KB Output is correct
18 Correct 334 ms 174508 KB Output is correct
19 Correct 458 ms 179272 KB Output is correct
20 Correct 457 ms 179412 KB Output is correct
21 Correct 503 ms 180068 KB Output is correct
22 Correct 271 ms 159704 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 98880 KB Output is correct
2 Correct 60 ms 98892 KB Output is correct
3 Correct 53 ms 99112 KB Output is correct
4 Incorrect 56 ms 99000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 98880 KB Output is correct
2 Correct 60 ms 98892 KB Output is correct
3 Correct 53 ms 99112 KB Output is correct
4 Incorrect 56 ms 99000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 98880 KB Output is correct
2 Correct 60 ms 98892 KB Output is correct
3 Correct 53 ms 99112 KB Output is correct
4 Incorrect 56 ms 99000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 98880 KB Output is correct
2 Correct 60 ms 98892 KB Output is correct
3 Correct 53 ms 99112 KB Output is correct
4 Incorrect 56 ms 99000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98948 KB Output is correct
2 Correct 49 ms 98908 KB Output is correct
3 Correct 53 ms 99056 KB Output is correct
4 Correct 62 ms 98932 KB Output is correct
5 Correct 59 ms 98896 KB Output is correct
6 Correct 50 ms 99052 KB Output is correct
7 Correct 50 ms 99056 KB Output is correct
8 Incorrect 50 ms 98944 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98892 KB Output is correct
2 Correct 50 ms 98928 KB Output is correct
3 Correct 53 ms 98900 KB Output is correct
4 Correct 71 ms 99032 KB Output is correct
5 Correct 100 ms 99544 KB Output is correct
6 Correct 52 ms 99116 KB Output is correct
7 Correct 52 ms 99028 KB Output is correct
8 Correct 58 ms 99176 KB Output is correct
9 Correct 117 ms 102416 KB Output is correct
10 Correct 211 ms 149684 KB Output is correct
11 Correct 71 ms 99128 KB Output is correct
12 Correct 120 ms 99712 KB Output is correct
13 Correct 362 ms 164872 KB Output is correct
14 Correct 415 ms 163024 KB Output is correct
15 Correct 695 ms 173420 KB Output is correct
16 Correct 1181 ms 216788 KB Output is correct
17 Correct 464 ms 182964 KB Output is correct
18 Correct 334 ms 174508 KB Output is correct
19 Correct 458 ms 179272 KB Output is correct
20 Correct 457 ms 179412 KB Output is correct
21 Correct 503 ms 180068 KB Output is correct
22 Correct 271 ms 159704 KB Output is correct
23 Correct 50 ms 98880 KB Output is correct
24 Correct 60 ms 98892 KB Output is correct
25 Correct 53 ms 99112 KB Output is correct
26 Incorrect 56 ms 99000 KB Output isn't correct
27 Halted 0 ms 0 KB -