Submission #1117576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117576		vjudge1	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2062 ms	33040 KiB

joi2019_ho_t5

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ordered_set tree < ll, null_type, less < ll > , rb_tree_tag, tree_order_statistics_node_update >
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 500001;

using namespace std;
using namespace __gnu_pbds;

ll n, m, a, b, c, p[N], ans, d[N], cnt[N], ls[N], num[N];
set <ll> s;
vector <ll> g[N];

ll binpow(ll a, ll b) {
    a %= mod;
    if (b == 0) {
        return 1;
    }
    else if (b % 2 == 1) {
        return binpow(a, b - 1) % mod * a % mod;
    }
    else {
        ll t = binpow(a, b / 2) % mod;
        return t * t % mod;
    }
}

void dfs (ll v, ll pr){
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pr){
			d[g[v][i]] = d[v] + 1;
			if (cnt[d[g[v][i]]]){
				num[ls[d[g[v][i]]]]--;
				if (ls[d[g[v][i]]] != -1 && num[ls[d[g[v][i]]]] == 0)s.erase(ls[d[g[v][i]]]);
				ls[d[g[v][i]]] = -1;
//				cout << "del " << d[g[v][i]] << ' ' << g[v][i] << ' ' << p[g[v][i]] << ' ' << s.size() << '\n';
			}
			else{
				cnt[d[g[v][i]]]++;
				num[p[g[v][i]]]++;
				s.insert(p[g[v][i]]);
//				cout << "add " << d[g[v][i]] << ' ' << g[v][i] << ' ' << p[g[v][i]] << ' ' << s.size() << '\n';
				ls[d[g[v][i]]] = p[g[v][i]];
			}
			dfs (g[v][i], v);
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb (b);
		g[b].pb (a);
	}
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	for (int i = 1; i <= n; i++){
		s.clear();
		d[i] = 1;
		dfs (i, i);
		for (int j = 1; j <= n; j++){
			cnt[j] = num[j] = 0;
		}
		cout << s.size() << '\n';
	}
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs(long long int, long long int)':
joi2019_ho_t5.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32