oj.uz

Submission #1055755

# Submission time Handle Problem Language Result Execution time Memory
1055755 2024-08-13T05:01:48 Z coolsentenceidontremember Training (IOI07_training) C++17
100 / 100
 7 ms 4700 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3", "unroll-loops")


#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok() cout << "it aight" << '\n'
using namespace std;



void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}

const int D = 10;
const int N = 1000;
int up[N][D+1];
int order[N];
int deg[N];
int depth[N];
pair<int, int> par[N];
int cnt = 0;
vector<int> adj[N];
struct edge{
	int u, v, c, lca;
	edge(int uu, int vv, int cc, int l = -1) : u(uu), v(vv), c(cc), lca(l){
		
	}
	bool operator < (const edge& other){
		return order[lca] < order[other.lca];
	}
};

vector<edge> edges;

void dfs(int u = 0, int p = 0){
//	cout << u << ' ' << p << '\n';
//	check_ok();
	up[u][0] = p;
	for (int i = 1; i <= D; i++){
		up[u][i] = up[up[u][i-1]][i-1];
	}
	for (int v : adj[u]){
		if (v==p) continue;
			depth[v] = depth[u]+1;
			par[v] = {u, 1<<deg[u]};
			deg[u]++;
			dfs(v, u);
	}
	order[u] = ++cnt;
}

int jump(int u, int h){
//	cout << "jumps ";
//	check_ok();
	for (int i = 0; i <= D; i++){
		if (h & (1<<i)) u = up[u][i];
	}
	return u;
}


int LCA(int a, int b){
//	cout << "lca ";
//	check_ok();
	if (depth[a] < depth[b]) swap(a, b);
	int dif = depth[a] - depth[b];
	a = jump(a, dif);
	if (a==b) return a;
	for (int i = D; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

int dp[N][1<<D], mask1, mask2;

void build(){
	//cout << "build ";
	//check_ok();
	for (const edge& e : edges){
		if ((depth[e.u]+depth[e.v])&1 && e.c) continue;
		int a = e.u, b = e.v, c = e.c, lca = e.lca;
	//	cout << a << ' ' << b << ' ' << lca << '\n';
		for (mask1 = 0; a != lca;tie(a, mask1) = par[a]){
			c += dp[a][mask1];
		} 
		for (mask2 = 0; b != lca; tie(b, mask2) = par[b]) c += dp[b][mask2];
		mask1 |= mask2;
		for (int mask = (1<<deg[lca])-1; mask >= 0; mask--){
			if (mask & mask1) continue;
			dp[lca][mask] = max(dp[lca][mask], c + dp[lca][mask|mask1]);
		}
	}
}

int main(){
  int n, m;
  cin >> n >> m;
  int sum = 0;
  for (int i = 1; i <= m; i++){
  	int a, b, cost;
  	cin >> a >> b >> cost;
  	a--; b--;
  	if (!cost){
  	adj[a].push_back(b);
  	adj[b].push_back(a);
	  }
  	
  	sum += cost;
  	edges.push_back(edge(a, b, cost));
  }
  memset(up, -1, sizeof up);
  memset(deg, 0, sizeof deg);
  depth[0] = 0;
  dfs();
  for (edge& e : edges){
  	if ((depth[e.u]+depth[e.v])&1 && e.c) continue;
  	e.lca = LCA(e.u, e.v);
  //	cout << e.u << ' ' << e.v << ' ' << e.lca << '\n';
  }
  sort(edges.begin(), edges.end());
  build();
  cout << sum - dp[0][0];
}
/*
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1 
*/

Compilation message

training.cpp: In function 'void setIO(std::string)':
training.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 1504 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2140 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 3 ms 1628 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2140 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 3 ms 1368 KB Output is correct