제출 #931649

#제출 시각아이디문제언어결과실행 시간메모리
931649vjudge1수도 (JOI20_capital_city)C++17
11 / 100
3045 ms184684 KiB
/// ITNOG #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define F first #define S second #define pb push_back #define ppb pop_back #define fast_io ios::sync_with_stdio(false);cin.tie(NULL); #define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #define FOR(i,k,n) for(int i = k; i < n; ++ i) #define debf cout<<"(0-0)\n"; #define all(x) x.begin(), x.end() #define dec(x) cout << fixed << setprecision(x); #define pf push_front #define ppf pop_front #define dash " ------- " #define what(x) cerr << #x << " is " << x << endl; #define eb emplace_back //#define int short int #define int long long #define sz(s) (int) (s.size()) #define fl cout.flush() using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <int, pii> pip; typedef pair <pii, int> ppi; typedef pair <ll, ll> pll; typedef unsigned long long ull; typedef long double ld; template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >; template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >; //template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 1e6, SQ = 600, INF = 1e15 + 8, LGN = 22, mod = 998244353, P = 131113; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); bool mark[N]; int n, k, col[N], st[N], xxx, sz; vector <int> adj[N]; vector <int> v[N]; bool dfs (int u, int par = -1){ bool ok = false; if (col[u] == xxx){ ok = true; } for (int i : adj[u]){ if (i != par){ ok |= dfs (i, u); } } if (ok){ if (col[u] != xxx){ v[xxx].pb(col[u]); } } return ok; } void dfs2 (int u){ mark[u] = true; //cout << xxx + 1 << " " << u + 1 << '\n'; ++ sz; for (int i : v[u]){ if (!mark[i]){ dfs2 (i); } } return; } int32_t main(){ fast_io; cin >> n >> k; FOR (i, 0, n - 1){ int aa, bb; cin >> aa >> bb; adj[--aa].pb(--bb); adj[bb].pb(aa); } FOR (i, 0, n){ cin >> col[i]; st[--col[i]] = i; } for (int i = 0; i < k; ++ i){ xxx = i; dfs (st[i]); sort (all(v[xxx])); v[xxx].resize(unique(all(v[xxx])) - v[xxx].begin()); } //cout << "--- " << v[2].size() << " " << v[2].back() + 1 << '\n'; int ans = 0; ans = 1000000; for (int i = 0; i < k; ++ i){ fill (mark, mark + 2008, false); sz = 0; xxx = i; dfs2 (i); ans = min (ans, sz - 1); } cout << ans; return 0; } // Yesterday is history // Tomorrow is a mystery // but today is a gift // That is why it is called the present
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...