oj.uz

Submission #239239

# Submission time Handle Problem Language Result Execution time Memory
239239 2020-06-14T23:14:07 Z frodakcin Synchronization (JOI13_synchronization) C++11
100 / 100
 333 ms 23544 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <functional>
#include <vector>
#include <set>

const int MN = 1e5+10, MM = 2e5+10;
struct edge
{
public:
	int n, id;
};
std::vector<edge> a[MN];
int N, M, Q, p[MN][1], s[MN], d[MN], h[MN], t[MN], l[MN], f[MN], m[MN], w[MN];
const auto cmp=[](int x, int y){return d[x]>d[y];};//decreasing level/depth. no collisions should occur because these are on heavy chains
typedef std::set<int, decltype(cmp)> Set;
Set *hv[MN];
bool u[MN];

void dfs(int n=1)
{
	s[n]=1;
	for(auto x:a[n])
		if(x.n!=p[n][0])
			m[x.id]=x.n, p[x.n][0]=n, d[x.n]=d[n]+1, dfs(x.n), s[n]+=s[x.n];
}
void dfs2(int n=1)
{
	for(auto x:a[n])
		if(x.n!=p[n][0])
		{
			if(s[x.n]*2>s[n])//>= is ok too
			{
				h[n]=x.n;
				if(!~t[n])
					t[n]=n, l[n]=0, hv[n]=new Set(cmp);
				t[x.n]=t[n], l[x.n]=l[n]+1;
			}
			dfs2(x.n);
		}
	if(~t[n])
		hv[t[n]]->insert(n);
}
int get(int n)
{
	for(;;)
		if(~t[n])
		{
			Set *set = hv[t[n]];
			auto it=set->lower_bound(n);
			if(it == set->end())
				n=p[t[n]][0];
			else
				return *it;
		}
		else if(u[n])
			n=p[n][0];
		else
			return n;
}
int main(void)
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1,x,y;i<N;++i)
		scanf("%d%d", &x, &y), a[x].push_back({y, i}), a[y].push_back({x, i});
	memset(t, -1, sizeof t);
	memset(h, -1, sizeof h);
	dfs();
	dfs2();
	for(int i=1;i<=N;++i) f[i]=1;
	for(int i=0,k;i<M;++i)
	{
		scanf("%d", &k);
		k = m[k];//child of affected edge
		if(u[k])
		{
			int c=f[get(k)];
			w[k]=f[k]=c;
			if(~t[k])
				hv[t[k]]->insert(k);
		}
		else
		{
			//assert(get(k) == k);
			f[get(p[k][0])]+=f[k]-w[k];//f[k] and w[k] can be set to nan
			if(~t[k])
				hv[t[k]]->erase(k);
		}
		u[k]^=1;
	}
	for(int i=0,k;i<Q;++i)
		scanf("%d", &k), printf("%d\n", f[get(k)]);
	for(int i=1;i<=N;++i)
		if(t[i]==i)
			delete hv[i];
	return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:66:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y), a[x].push_back({y, i}), a[y].push_back({x, i});
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
synchronization.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k), printf("%d\n", f[get(k)]);
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 8 ms 3456 KB Output is correct
3 Correct 7 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 17 ms 4608 KB Output is correct
8 Correct 17 ms 4608 KB Output is correct
9 Correct 16 ms 4608 KB Output is correct
10 Correct 166 ms 15104 KB Output is correct
11 Correct 159 ms 15096 KB Output is correct
12 Correct 270 ms 22648 KB Output is correct
13 Correct 72 ms 11756 KB Output is correct
14 Correct 118 ms 14072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 16888 KB Output is correct
2 Correct 94 ms 16628 KB Output is correct
3 Correct 118 ms 21704 KB Output is correct
4 Correct 110 ms 21752 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 7 ms 3456 KB Output is correct
6 Correct 8 ms 3712 KB Output is correct
7 Correct 25 ms 5504 KB Output is correct
8 Correct 307 ms 23432 KB Output is correct
9 Correct 303 ms 23416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 23544 KB Output is correct
2 Correct 131 ms 22904 KB Output is correct
3 Correct 135 ms 22908 KB Output is correct
4 Correct 135 ms 22904 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 19 ms 4736 KB Output is correct
7 Correct 222 ms 15992 KB Output is correct
8 Correct 305 ms 23416 KB Output is correct
9 Correct 95 ms 12904 KB Output is correct
10 Correct 170 ms 15356 KB Output is correct
11 Correct 117 ms 18036 KB Output is correct
12 Correct 130 ms 18036 KB Output is correct
13 Correct 143 ms 22904 KB Output is correct