Submission #999399

#TimeUsernameProblemLanguageResultExecution timeMemory
999399vjudge1LOSTIKS (INOI20_lostiks)C++17
0 / 100
32 ms27988 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]; } vector<array<int,3>> c; bool check(int x,int y,int z){ bool ok=true; for(int i=0;i<cnt;i++){ if(!(x&(1<<i))){ int h1,h2,h3; h1=lca(c[i][0],y); h2=lca(c[i][0],z); h3=lca(y,z); if((h1==c[i][0] && dep[h1]>dep[h3]) || (h2==c[i][0] && dep[h2]>dep[h3])){ ok=false; } } } return ok; } 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); } } int dp[1<<20][21]; void solve(){ cin >> n; g.clear(); g.resize(n+1); cin >> m >> k; 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 h=(1<<cnt); for(int i=0;i<h;i++){ for(int j=0;j<=cnt;j++){ dp[i][j]=INF; } } dp[0][cnt]=0; int res=INF; for(int i=0;i<h;i++){ for(int j=0;j<=cnt;j++){ if(dp[i][j]==INF){ continue; } int num; if(j==cnt){ num=m; } else{ num=a[c[j][2]]; } for(int z=0;z<cnt;z++){ if(!(i&(1<<z)) && check(i,num,a[c[z][2]])){ dp[i+(1<<z)][z]=min(dp[i+(1<<z)][z],dp[i][j]+dep[num]+dep[a[c[z][2]]]-2*dep[lca(num,a[c[z][2]])]); } } if(check(i,num,k)){ res=min(res,dp[i][j]+dep[num]+dep[k]-2*dep[lca(num,k)]); } } } 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++; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...