Submission #915280

#TimeUsernameProblemLanguageResultExecution timeMemory
915280AmrVillage (BOI20_village)C++14
0 / 100
3 ms7516 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define S second #define F first #define all(x) (x).begin(),(x).end() #define sz size() #define Yes cout << "YES" << endl #define No cout << "NO" << endl #define pb(x) push_back(x); #define endl '\n' #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int N=3e5+7; ll INF=INT_MAX,mod=1e9+7; int TT=1; ll power(ll x, unsigned int y) { ll res = 1; x = x; // % mod; if (x == 0) return 0; while (y > 0) { if (y & 1) res = (res*x) ; // % mod; y = y>>1; x = (x*x) ; // % mod; } return res; } ll ans = 0; vector<ll> v[N]; ll mxdep = 0; void dfs(ll x, ll par, ll dep) { mxdep = max(dep,mxdep); if(dep&1) ans++; for(int i = 0; i < v[x].sz; i++) { ll newn = v[x][i]; if(newn==par) continue; dfs(newn,x,dep+1); } } ll best[N]; void dfs2(ll x, ll par, ll dep) { if(dep&1) { ll lst = x; if(v[x].back()==par) best[x] = v[x][v[x].sz-2]; else best[x] = v[x].back(); for(int newn : v[x]) { if(newn==par) continue; best[newn] = lst; lst = newn; } } for(int newn: v[x]) { if(newn==par) continue; dfs2(newn,x,dep+1); } } void solve() { ll n; cin >> n; for(int i = 0; i < n-1; i++) { ll x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } ll mn = 1e18, cnt; for(int i = 1; i <= n ;i++) { ans = 0; mxdep = 0; dfs(i,0,1); if(mxdep%2==1) continue; // cout << i << " " << ans << " "; ans = (2*ans) + (n-2*ans)*2; //cout << ans << endl; if(ans<mn) { cnt = i , mn= ans;} } dfs2(cnt,0,1); cout << mn << endl; for(int i = 1; i <= n; i++) { cout << best[i] << " "; } cout << endl; cout << 1 << endl; for(int i = 1; i <= n; i++) cout << 1 << endl; } int main(){ //freopen("friday.in","r",stdin); //freopen("friday.out","w",stdout); fast; //cin >> TT; while(TT--) solve(); return 0; }

Compilation message (stderr)

Village.cpp: In function 'void dfs(ll, ll, ll)':
Village.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
Village.cpp: In function 'void solve()':
Village.cpp:89:9: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     dfs2(cnt,0,1);
      |     ~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...