#include <bits/stdc++.h>
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const long long inf = 1e18;
struct edge
{
int u, v, w;
bool operator== (edge o){
return u == o.u && v == o.v && w == o.w;
}
bool operator!= (edge o){
return !(*this == o);
}
};
struct sliding_maximum
{
deque<pair<long long, int> > qu;
int i, l;
sliding_maximum(int _l){
i = 0;
l = _l;
}
long long getmax(){
if(qu.empty()) return -inf;
return qu.front().first;
}
void slide(long long newval){
while(!qu.empty()&&newval > qu.back().first){
qu.pop_back();
}
qu.push_back({newval,i});
if(qu.front().second<=i-l){
qu.pop_front();
}
i++;
}
};
int N;
vector<edge> edgelist; //12 MB
vector<vector<int> > graph; //8 MB (16 MB worst case)?
vector<bool> vis; //1 MB
bool flag = false;
int dfs(int id, vector<int>& cycle){
edge p = edgelist[id];
H(p.u); H(p.v); H(p.w);
//F(ii, 1e8);
if(vis[p.v]&&flag){
P("return 1");
return -1;
}
if(vis[p.v]){
flag = true;
P("return 2");
P("cyclee: "<<p.v);
H(id);
cycle.push_back(id);
return p.v;
}
vis[p.v] = true;
int ce = -1;
for(int i : graph[p.v]) if(id != (i^1)) {
int a = dfs(i, cycle);
if(a!=-1) ce = a;
}
if(ce == p.v){
//cycle.push_back(cycle[0]);
P("return 3");
return -1;
}
if(ce != -1){
P("cycle: "<<p.v);
H(id);
cycle.push_back(id);
}
P("return 4: "<<ce);
return ce;
}
void dfs2(int id, int d, int& f1, int& f2, int& maxu, int& maxd){
//F(i, 1e8);
edge p = edgelist[id];
H(p.u); H(p.v); H(p.w);
H(id); H(f1); H(f2);
if(d>maxd){
maxu = p.v;
maxd = d;
P("update (maxu, maxd) to");
H(maxu); H(maxd);
}
//int d = 0;
for(int i : graph[p.v]) if(i-i%2 != id-id%2 && i-i%2 != f1-f1%2 && i-i%2 != f2-f2%2){
dfs2(i, d+edgelist[i].w, f1, f2, maxu, maxd);
}
//return d+p.w;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//input
cin>>N;
edgelist.resize(2*N+1);
graph.resize(N);
F(u, N){
int v,w;
cin>>v>>w;
v--;
edgelist[2*u] = {u, v, w};
graph[u].push_back(2*u);
edgelist[2*u+1] = {v, u, w};
graph[v].push_back(2*u+1);
}
//loop to calculate everything
vis.resize(N, 0);
edgelist[2*N] = {-1, 0, 0};
int sum = 0;
F(t, N) if(!vis[t]){
P("--------------------------------------------");
H(t);
int maxtot = 0;
vector<int> cycle; //4MB
flag = false;
edgelist[2*N].v = t;
dfs(2*N, cycle);
int c = cycle.size();
reverse(cycle.begin(), cycle.end()); //(0,1), (1,2), ..., (c-1, 0)
P("step 1");
for(int i : cycle){
edge p = edgelist[i];
P("cycle edge "<<i);
H(p.u);
H(p.v);
H(p.w);
}
vector<long long> d(c, 0); //8MB
F(i, c){
H(i);
edge p = edgelist[cycle[i]];
int f1 = cycle[(i-1+c)%c];
int f2 = cycle[i];
edgelist[2*N].v = p.u;
int maxu = -1, maxd = -1;
P("root: "<<p.u);
dfs2(2*N, 0, f1, f2, maxu, maxd);
d[i] = maxd;
int maxu2 = -1, maxd2 = -1;
edgelist[2*N].v = maxu;
P("root2: "<<maxu);
dfs2(2*N, 0, f1, f2, maxu2, maxd2);
maxtot = max(maxtot, maxd2);
}
H(maxtot);
P("step 2");
vector<int> pref(c*2+1, 0);
F(i, c){
pref[i+1] = pref[i] + edgelist[cycle[i%c]].w;
}
P("step 3");
sliding_maximum sm(c-1);
H(c);
for(int i = 2*c-1; i>=0; i--){
H(i);
maxtot = max((long long)maxtot, sm.getmax()-pref[i]+d[i%c]);
sm.slide(pref[i]+d[i%c]);
}
P("step 4");
H(maxtot);
sum += maxtot;
}
cout<<sum<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
380 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
6776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
20444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
38768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
445 ms |
98160 KB |
Output is correct |
| 2 |
Incorrect |
1354 ms |
131072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
504 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
