Submission #999229

#TimeUsernameProblemLanguageResultExecution timeMemory
999229vjudge1LOSTIKS (INOI20_lostiks)C++17
0 / 100
2076 ms29348 KiB
#include <bits/stdc++.h> //#define int ll #define MAX 1000001 #define INF INT_MAX #define MOD 1000000007 #define mp make_pair #define mt make_tuple #define pb push_back #define ins insert #define ff first #define ss second #define all(a) a.begin(),a.end() #define lb(a,b) lower_bound(all(a),b) #define ub(a,b) upper_bound(all(a),b) #define sortv(a) sort(all(a)) #define outputar(a,b){\ for(int i=0;i<b;i++){\ cout << a[i] << " ";\ }\ cout << endl;\ } #define outputvec(a){\ for(auto x:a){\ cout << (int)x << " ";\ }\ cout << endl;\ } #define reset(a,n,v){\ for(int i=0;i<n;i++){\ a[i]=v;\ }\ } using namespace std; typedef long long ll; typedef unsigned long long ull; typedef tuple<ll,ll,ll> tll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef double db; typedef long double ldb; inline void USACO(string filename){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],d[MAX]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //string s[MAX],str[MAX]; //int e[1001][1001]; string s1,s2,s3; const int mod = 998244353; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; vector<vector<int>> g; int st[MAX][20],dep[MAX],pre[MAX],cnt=0; int lca(int x,int y){ if(dep[x]<dep[y]){ swap(x,y); } int h=dep[x]-dep[y]; for(int i=0;i<20;i++){ if((h&(1<<i))){ x=st[x][i]; } } if(x==y){ return x; } for(int i=19;i>=0;i--){ if(st[x][i]!=st[y][i]){ x=st[x][i]; y=st[y][i]; } } return pre[x]; } void dfs(int v,int prev){ st[v][0]=prev; pre[v]=prev; for(auto x:g[v]){ if(x==prev){ continue; } dep[x]=dep[v]+1; dfs(x,v); } } void solve(){ cin >> n; g.clear(); g.resize(n+1); cin >> m >> k; vector<array<int,3>> c; for(int i=0;i<n-1;i++){ cin >> x >> y >> z; g[x].pb(y); g[y].pb(x); a[i]=z; if(a[i]!=0){ c.pb({x,y,i}); cnt++; } } dfs(1,-1); for(int i=1;i<20;i++){ for(int j=1;j<=n;j++){ if(st[j][i-1]!=-1){ st[j][i]=st[st[j][i-1]][i-1]; } } } for(int i=0;i<cnt;i++){ int n1,n2; n1=c[0][0]; n2=c[0][1]; if(dep[n1]<dep[n2]){ swap(n1,n2); } c.pb({n1,n2,c[0][2]}); c.erase(c.begin()); } int res=INF; do{ for(auto x:c){ b[x[2]]=0; d[x[2]]=0; } int res1=0; int h,h1,h2; h=m; h2=0; int cnt1=1,cnt2=0; set<array<int,3>> e; h1=lca(m,k); for(auto x:c){ int h3,h4; h3=lca(x[0],m); h4=lca(x[0],k); if((h3==x[0] && dep[h3]>dep[h1]) || (h4==x[0] && dep[h4]>dep[h1])){ e.ins({cnt1,cnt-cnt2,x[2]}); d[x[2]]=cnt1; } cnt2++; } int cnt3=0; while(e.size()>0){ cnt1++; cnt2=0; bool ok=false; array<int,3> p=*(--e.end()); h1=lca(a[p[2]],h); for(auto x:c){ if(b[x[2]]==1){ continue; } int h3,h4; h3=lca(x[0],a[p[2]]); h4=lca(x[0],h); if((h3==x[0] && dep[h3]>dep[h1]) || (h4==x[0] && dep[h4]>dep[h1])){ if(d[x[2]]!=0){ e.erase({d[x[2]],cnt-cnt2,x[2]}); } e.ins({cnt1,cnt-cnt2,x[2]}); ok=true; } cnt2++; } if(!ok){ res1+=dep[h]+dep[a[p[2]]]-2*dep[h1]; e.erase(p); b[p[2]]=1; h=a[p[2]]; } if(cnt3==100000){ res1=INF; break; } cnt3++; } if(res1!=INF){ h1=lca(h,k); res1+=dep[h]+dep[k]-2*dep[h1]; } res=min(res,res1); }while(next_permutation(all(c))); if(res==INF){ res=-1; } cout << res << "\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("input13.txt","r",stdin); //cin >> t; ll cnt1=1; while(t--){ solve(); cnt1++; } }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:128:18: warning: variable 'h2' set but not used [-Wunused-but-set-variable]
  128 |         int h,h1,h2;
      |                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...