| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 770004 |
2023-06-30T16:20:36 Z |
vjudge1 |
Paths (RMI21_paths) |
C++17 |
|
208 ms |
23500 KB |
#include <bits/stdc++.h>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e9+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int l = 25;
void readio(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
ve<pair<int,ll>> adj[nax];
bool vis[nax];
ll mxs[nax], dep[nax];
int up[nax][l];
int timer = 0, tin[nax], tout[nax];
ll dfs(int u, int p){
tin[u] = ++timer;
up[u][0] = p;
for (int i = 1; i <= l; ++i)
up[u][i] = up[up[u][i-1]][i-1];
for(auto x : adj[u]){
if(x.fi == p) continue;
dep[x.fi] = dep[u]+x.se;
if(!vis[x.fi]) mxs[u] = max(mxs[u], dfs(x.fi,u)+x.se);
else mxs[u] = max(mxs[u], dfs(x.fi, u));
}
tout[u] = ++timer;
//cout << u << " " << mx << endl;
return mxs[u];
}
bool ass(int u, int p, ll path, ll mx){
if(path == mx) return 1;
for(auto x : adj[u]){
if(x.fi == p) continue;
ll cur = path;
if(!vis[x.fi]) cur += x.se;
if(ass(x.fi,u,cur,mx)){
vis[x.fi] = 1;
return 1;
}
}
return 0;
}
ii ans;
bool isAnc(int u, int v){
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v)
{
if (isAnc(u, v))
return u;
if (isAnc(v, u))
return v;
for (int i = l; i >= 0; --i) {
if (!isAnc(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
ll distance(int a, int b){
int c = lca(a,b);
//cout << a << " " << dep[a] << " " << b << " " << dep[b] << endl;
return (dep[a]+dep[b]-2*dep[c]);
}
void diam(int u, int p, int cur){
if(ans.fi < cur) ans.fi = cur, ans.se = u;
for(auto x : adj[u]){
if(x.fi == p) continue;
diam(x.fi, u, cur+x.se);
}
}
int main()
{
optimise;
int n, k;
cin >> n >> k;
for(int i = 0; i < n-1; i++){
int a,b,c;
cin >> a >> b >> c;
a--,b--;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
if(k == 1){
dfs(0,0);
int a,b;
ans = {0,0};
diam(0,0,0);
a = ans.se;
ans = {0,0};
diam(a,a,0);
b = ans.se;
for (int i = 0; i < n; ++i)
{
//cout << distance(b,i) << " " << distance(a,i) << endl;
cout << max(distance(a,i), distance(b,i)) << endl;
}
return 0;
}
for (int i = 0; i < n; ++i)
{
ll mx = 0;
memset(vis,0, sizeof vis);
for (int j = 0; j < k; ++j)
{
ll cur = dfs(i,i);
mx += cur;
ass(i,i, 0, cur);
}
cout << mx << endl;
}
}
Compilation message
Main.cpp: In function 'void readio()':
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'long long int dfs(int, int)':
Main.cpp:36:18: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
36 | up[u][i] = up[up[u][i-1]][i-1];
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:35:23: note: within this loop
35 | for (int i = 1; i <= l; ++i)
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
23500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
