Submission #635371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
635371	2022-08-26T07:15:29 Z	MohammadAghil	LOSTIKS (INOI20_lostiks)	C++17	Compilation error	0 ms	0 KB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}

const ll mod = 1e9 + 7, maxn = 1e6 + 5, maxm = 20, inf = ll(1e18) + 5;

int val[maxn], ed[maxm], nxt[maxm], tmp;
vector<pp> adj[maxn];

void dfs(int r, int p, int v){
    val[r] = v;
    for(auto[c, w]: adj[r]) if(c - p){
        if(w + 1){
            ed[tmp] = r;
            nxt[tmp] = w;
            tmp++;
            dfs(c, r, v|(1<<(tmp-1)));
        } else{
            dfs(c, r, v);
        }
    }
}

int dist[maxm + 5][maxn];

void dfs2(int r, int p, int id){
    for(auto[c, w]: adj[r]) if(c - p){
        dist[id][c] = dist[id][r] + 1;
        dfs2(c, r, id);
    }
}

int dp[1<<maxm][maxm];

int main(){ IOS();
    int n, s, t; cin >> n >> s >> t; s--, t--;
    int m = 0;
    rep(i,1,n){
        int u, v, w; cin >> u >> v >> w; u--, v--, w--;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        m += w != -1;
    }
    dfs(s, -1, 0);
    rep(i,0,m){
        dfs2(ed[i], -1, i);
    }
    dfs2(s, -1, m);
    auto chk = [&](int msk, int r){
        return (val[r]&msk) == val[r];
    };
    per(i,(1<<m)-1,1){
        rep(e,0,m){
            dp[i][e] = inf;
            int r = ed[e];
            if((i>>e&1) && chk(i, r)){
                if(chk(i, t)){
                    dp[i][e] = dist[e][t];
                }else{
                    rep(x,0,m) if(!(i>>x&1) && chk(i, nxt[x]) && chk(i, ed[x])){
                        dp[i][e] = min(dp[i][e], dp[i^(1<<x)][x] + dist[e][nxt[x]] + dist[x][nxt[x]]);
                    }
                }
            }
        }
    }
    ll ans = inf;
    rep(i,0,m){
        if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
    }
    if(chk(0, t)){
        ans = dist[m][t];
    }
    cout << (ans == inf? -1: ans) << '\n';
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:83:24: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000005' to '-1486618619' [-Woverflow]
   83 |             dp[i][e] = inf;
      |                        ^~~
Main.cpp:98:107: error: no matching function for call to 'min(ll&, int)'
   98 |         if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
      |                                                                                                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
Main.cpp:98:107: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   98 |         if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
      |                                                                                                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
Main.cpp:98:107: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   98 |         if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
      |                                                                                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
Main.cpp:98:107: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   98 |         if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
      |                                                                                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
Main.cpp:98:107: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   98 |         if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
      |                                                                                                           ^
Main.cpp: In function 'void IOS()':
Main.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("inp.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~