Submission #1280794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280794		tdkhai	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	1310 ms	588248 KiB

Main

/*
        _.-- ,.--.
      .'   .'     /
       @       |'..--------._
     /      \._/              '.
    /  .-.-                     \
   (  /    \                     \
   \\      '.                  | #
    \\       \   -.           /
     :\       |    )._____.'   \
      "       |   /  \  |  \    )
              |   |./'  :__ \.-'
              '--'
*/
#include<bits/stdc++.h>
#define ll long long
#define llll pair<ll,ll>
#define ii pair<int,int>
#define fi first
#define se second
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define ull unsigned long long
#define iii pair<int,ii>
#define iv pair<pii,ii>
#define db double
#define ld long double
#define pb push_back
#define tdk "kfph"


using namespace std;

const int dx[]  = {1, -1, 0, 0};
const int dy[]  = {0, 0, -1, 1};
const int dxx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyy[] = {2, -2, 2, -2, 1, -1, 1, -1};
const ll INF=1e18;


const int N=1e6+5;
ll dp[20][1<<20],Lock[N];
int n,s,t,h[N],key[N],target[N],cnt,m,tin[N],tout[N];
vector<ii> a[N],LCK;
int K,LG,times;
vector<pair<ii,int>> lks;
ii ST[21][N*2];
void dfs(int u,int par)
{
    LCK.pb({h[u],u});
    tin[u]=times++;
    for(int i=0;i<a[u].size();i++)
    {
        int v=a[u][i].fi,w=a[u][i].se;
        if(v==par) continue;
        Lock[v]=(Lock[u]^w);
        h[v]=h[u]+1;
        dfs(v,u);
        LCK.pb({h[u],u});
     }
     tout[u]=times++;
}
void prepare()
{
    LG=__lg(LCK.size());
    for(int i=0;i<LCK.size();i++)
    {
        ST[0][i]=LCK[i];
//        cout << LCK[i].fi << ' ' << LCK[i].se <<'\n';
    }
    for(int i=1;i<=LG;i++)
    {
        for(int j=0;j+(1<<i)-1<LCK.size();j++)
        {
            ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
        }
    }
}
int lca(int u,int v)
{
    if(tin[u]>tin[v]) swap(u,v);
    int L=__lg(tin[v]-tin[u]+1);
    return min(ST[L][tin[u]],ST[L][tin[v]-(1<<L)+1]).se;
}
int dist(int u,int v)
{
    return h[u]+h[v]-2*h[lca(u,v)];
}
bool cango(int u,int v,int mask)
{
    int msk=(Lock[u]^Lock[v]);
    return ((msk&mask)==msk);
}
void kfph()
{
    cin >> n >> s >> t;
    for(int i=1;i<n;i++)
    {
        int u,v,H;
        cin >> u >> v >> H;
        if(H)
        {
            a[u].pb({v,1<<cnt});
            a[v].pb({u,1<<cnt});
            lks.pb({{u,v},H});
            cnt++;
        }
        else
        {
            a[u].pb({v,0});
            a[v].pb({u,0});
        }
    }
    m=cnt;
    dfs(s,-1);
    K=LCK.size();
    prepare();
    for(int i=0;i<m;i++)
    {
        int u=lks[i].fi.fi,v=lks[i].fi.se,k=lks[i].se;
        key[i]=k;
        if(dist(u,s)>dist(v,s))
        {
            target[i]=v;
        }
        else target[i]=u;
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<1<<m;j++)
        {
            dp[i][j]=INF;
        }
    }
    if(cango(s,t,0))
    {
        cout << dist(s,t);
        return;
    }
    for(int i=0;i<m;i++)
    {
        if(cango(s,key[i],0) and cango(key[i],target[i],0))
        {
            dp[i][1<<i]=dist(s,key[i])+dist(key[i],target[i]);
        }
    }
    ll ans=INF;
    for(int mask=0;mask<(1<<m);mask++)
    {
        vector<int> on,off;
        for(int j=0;j<m;j++)
        {
            if((mask>>j)&1)
            {
                on.pb(j);
            }
            else off.pb(j);
        }
        for(int i:on)
        {
            if(dp[i][mask]==INF) continue;
            if(cango(target[i],t,mask)) ans=min(ans,dp[i][mask]+dist(target[i],t));
            for(int j:off)
            {
                if(cango(target[i],key[j],mask) and cango(key[j],target[j],mask))
                {
                    dp[j][(mask|(1<<j))]=min(dp[j][(mask|(1<<j))],dp[i][mask]+dist(target[i],key[j])+dist(key[j],target[j]));
                }
            }
        }
    }
    if(ans==INF) ans=-1;
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
//    cin >> t;
    while(t--)
    {
        kfph();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41