Submission #633779

#	Time	Username	Problem	Language	Result	Execution time	Memory
633779		NothingXD	LOSTIKS (INOI20_lostiks)	C++14	Compilation error	0 ms	0 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:21: error: invalid operands of types 'const char [7]' and 'int' to binary 'operator&'
   67 |      scanf("%d%d%d" &n, &S, &T);
      |            ~~~~~~~~ ^~
      |            |         |
      |            |         int
      |            const char [7]
Main.cpp:141:74: error: expected ')' before ';' token
  141 |      printf("%d\n", (dp[(1 << m) - 1][m] == inf? -1: dp[(1 << m) - 1][m]);
      |            ~                                                             ^
      |                                                                          )
Main.cpp:69:25: 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);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~