제출 #1017701

#제출 시각아이디문제언어결과실행 시간메모리
1017701ByeWorldMergers (JOI19_mergers)C++14
100 / 100
937 ms239424 KiB
#include <bits/stdc++.h> // #pragma GCC optimize("O3", "unroll-loops") #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii, int> ipii; const int MAXN = 5e5+10; const int MAXA = 9e3+20; const ll INF = 1e9+10; const int LOG = 20; const int SQRT = 450; const vector<int> NOL = {}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; vector <int> key = {29, 31}; vector <int> mod = {998244353, 1000000007}; void chmx(int &a, int b){ a = max(a, b); } int n, k; vector <int> adj[MAXN], vec[MAXN]; int a[MAXN], tot[MAXN], u[MAXN], v[MAXN]; struct dsu { int par[MAXN], siz[MAXN]; void bd(){ for(int i=1; i<=n; i++){ par[i] = i; siz[i] = 1; } } int f(int x){ if(par[x]==x) return x; return par[x] = f(par[x]); } bool con(int x, int y){ return f(x) == f(y); } void mer(int x, int y){ x = f(x); y = f(y); if(x==y) return; if(siz[x] > siz[y]) swap(x, y); par[x] = y; siz[y] += siz[x]; } } DSU; int anc[MAXN][LOG+5], dep[MAXN], in[MAXN], tim; void dfs(int nw, int par){ anc[nw][0] = par; dep[nw] = dep[par]+1; in[nw] = ++tim; for(auto nx : adj[nw]){ if(nx==par) continue; dfs(nx, nw); } } int LCA(int x, int y){ if(dep[x] > dep[y]) swap(x, y); for(int i=LOG-1; i>=0; i--){ if(dep[anc[y][i]] >= dep[x]) y = anc[y][i]; } if(x==y) return x; for(int i=LOG-1; i>=0; i--){ if(anc[y][i] != anc[x][i]){ y = anc[y][i]; x = anc[x][i]; } } return anc[x][0]; } int cnt[MAXN]; vector <int> edge[MAXN]; bool cmp(int a, int b){ return in[a] < in[b]; } int ANS(int nw, int par){ for(auto nx : adj[nw]){ if(nx==par) continue; cnt[nw] += ANS(nx, nw); } return cnt[nw]; } signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k; DSU.bd(); for(int i=1; i<=n-1; i++){ int x, y; cin >> x >> y; u[i] = x; v[i] = y; adj[x].pb(y); adj[y].pb(x); } for(int i=1; i<=n; i++){ cin >> a[i]; tot[a[i]]++; vec[a[i]].pb(i); } dfs(1, 0); for(int j=1; j<LOG; j++) for(int i=1; i<=n; i++) anc[i][j] = anc[anc[i][j-1]][j-1]; for(int i=1; i<=k; i++){ if(vec[i].size() <= 1) continue; sort(vec[i].begin(), vec[i].end(), cmp); for(int j=1; j<vec[i].size(); j++){ cnt[LCA(vec[i][j-1], vec[i][j])] += 2; cnt[vec[i][j-1]]--; cnt[vec[i][j]]--; } cnt[LCA(vec[i][0], vec[i].back())] += 2; cnt[vec[i][0]]--; cnt[vec[i].back()]--; } ANS(1, 0); for(int i=1; i<=n; i++) if(cnt[i]) DSU.mer(i, anc[i][0]); for(int i=1; i<=n-1; i++){ int x = DSU.f(u[i]), y = DSU.f(v[i]); if(x == y) continue; edge[x].pb(y); edge[y].pb(x); } int tot = 0; for(int i=1; i<=n; i++){ if(edge[i].size() == 1) tot++; } cout << (tot+1)/2 << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:104:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j=1; j<vec[i].size(); j++){
      |                ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...