Submission #633782

#	Time	Username	Problem	Language	Result	Execution time	Memory
633782		NothingXD	LOSTIKS (INOI20_lostiks)	C++17	59 / 100	2053 ms	196264 KiB

Main

        #include<bits/stdc++.h>
        using namespace std;
         
        typedef long long ll;
        typedef long double ld;
        typedef unsigned long long ull;
        //typedef __uint128_t L;
        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
         
        void debug_out() { cerr << endl; }
         
        template <typename Head, typename... Tail>
        void debug_out(Head H, Tail... T) {
        	cerr << " " << H;
        	debug_out(T...);
        }
         
        #define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
        #define all(x) x.begin(), x.end()
        #define MP(x, y) make_pair(x, y)
        #define F first
        #define S second
         
        const int maxn = 1e6 + 10;
        const int maxm = 20;
        const int mask = (1 << 20);
        const int inf = 1e9;
         
        int n, m, S, T, edge[maxm][3], comp[maxn], cnt, sz, par[mask][maxm+1], h[maxm+1][maxn], dp[mask][maxm+1];
        vector<int> g[maxn], G[maxm+1];
        bool vis[maxn];
         
        int first[maxn], to[maxn << 1], nxt[maxn << 1], ecnt;
         
        void add(int u, int v){
        	nxt[++ecnt] = first[u];
        	to[ecnt] = v;
        	first[u] = ecnt;
        }
         
        void dfs(int v, int *h, int p = -1){
        	for (int i = first[v]; i; i = nxt[i]){
        		int u = to[i];
        		if (u != p){
        			h[u] = h[v] + 1;
        			dfs(u, h, v);
        		}
        	}
        }
         
        void getcomp(int v, int p = -1){
        	vis[v] = true;
        	comp[v] = cnt;
        	for (auto u: g[v]) if (u != p) getcomp(u, v);
        }
         
        void getpar(int v, int *par, int p = -1){
        	vis[v] = true;
        	par[v] = sz;
        	for (auto u : G[v]) if (u != p) getpar(u, par, v);
        }
         
        int main(){
        	//ios_base::sync_with_stdio(false); cin.tie(0);
         
        	scanf("%d%d%d", &n, &S, &T);
        	for (int i = 1; i < n; i++){
        		int u, v, w; scanf("%d%d%d", &u, &v, &w);
        		add(u, v);
        		add(v, u);
        		if (w == 0){
        			g[u].push_back(v);
        			g[v].push_back(u);
        		}
        		else{
        			edge[m][0] = u;
        			edge[m][1] = v;
        			edge[m][2] = w;
        			m++;
        		}
        	}
         
        	dfs(S, h[m]);
         
        	for (int i = 0; i < m; i++){
        		if (h[m][edge[i][0]] > h[m][edge[i][1]]) swap(edge[i][0], edge[i][1]);
        		dfs(edge[i][0], h[i]);
        	}
         
        	assert(m <= 20);
         
        	for (int i = 1; i <= n; i++){
        		if (!vis[i]){
        			getcomp(i);
        			cnt++;
        		}
        	}
         
        	for (int i = 0; i < (1 << m); i++){
        		for (int j = 0; j < m+1; j++){
        			G[j].clear();
        			vis[j] = false;
        		}
        		for (int j = 0; j < m; j++){
        			if (!((i >> j) & 1)){
        				G[comp[edge[j][0]]].push_back(comp[edge[j][1]]);
        				G[comp[edge[j][1]]].push_back(comp[edge[j][0]]);
        			}
        		}
        		sz = 0;
        		for (int j = 0; j < m+1; j++){
        			if (!vis[j]){
        				sz++;
        				getpar(j, par[i]);
        			}
        		}
        	}
         
        	for (int i = 0; i <= m; i++){
        		dp[0][i] = h[i][T];
        	}
         
        	for (int msk = 1; msk < (1 << m); msk++){
        		for (int i = 0; i <= m; i++){
        			int v = (i == m? S: edge[i][0]);
        			dp[msk][i] = inf;
        			if (par[msk][comp[T]] == par[msk][comp[v]]){
        				dp[msk][i] = h[i][T];
        				continue;
        			}
        			for (int tmp = msk; tmp; tmp ^= tmp & -tmp){
        				int j = __builtin_ctz(tmp);
        				if (par[msk][comp[edge[j][2]]] == par[msk][comp[v]] && par[msk][comp[edge[j][0]]] == par[msk][comp[v]]){
        					dp[msk][i] = min(dp[msk][i], dp[msk^(1 << j)][j] + h[i][edge[j][2]] + h[j][edge[j][2]]);
        				}
        			}
        		}
        	}
         
        	printf("%d\n", (dp[(1 << m) - 1][m] == inf? -1: dp[(1 << m) - 1][m]));
         
         
         
        	return 0;
        }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |          scanf("%d%d%d", &n, &S, &T);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |           int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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