| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105564 |
2019-04-13T13:44:02 Z |
Pro_ktmr |
Lamps (JOI19_lamps) |
C++14 |
|
7 ms |
5120 KB |
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back
struct UnionFind{
private:
int N;
vector<int> par;
public:
void init(int n){
N = n;
par.clear();
for(int i=0; i<N; i++) par.PB(i);
}
int root(int a){
if(par[a] == a) return a;
return par[a] = root(par[a]);
}
void unite(int a, int b){
a = root(a);
b = root(b);
if(a != b) par[b] = a;
}
bool same(int a, int b){
return (root(a) == root(b));
}
};
//RmaxQ RAD
struct SegmentTree{
private:
int N;
vector<LL> node,lazy;
public:
void init(int n){
N = 1;
while(N < n) N *= 2;
node.clear();
for(int i=0; i<2*N-1; i++) node.PB(0LL);
lazy.clear();
for(int i=0; i<2*N-1; i++) lazy.PB(0LL);
}
void eval(int k, int l, int r){
if(lazy[k] == 0LL) return;
node[k] += lazy[k];
if(r-l != 1){
lazy[2*k+1] += lazy[k];
lazy[2*k+2] += lazy[k];
}
lazy[k] = 0;
}
void add(int a, int b, LL x, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
lazy[k] += x;
eval(k, l, r);
}
else{
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
node[k] = max(node[2*k+1], node[2*k+2]);
}
}
pair<LL,int> maximum(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r <= a || b <= l) return MP(-1,-1);
if(r-l == 1) return MP(node[k], k-(N-1));
if(a <= l && r <= b){
eval(2*k+1, l, (l+r)/2);
eval(2*k+2, (l+r)/2, r);
if(node[2*k+1] > node[2*k+2]) return maximum(a, b, 2*k+1, l, (l+r)/2);
else return maximum(a, b, 2*k+2, (l+r)/2, r);
}
else return max(maximum(a, b, 2*k+1, l, (l+r)/2), maximum(a, b, 2*k+2, (l+r)/2, r));
}
void print(){
for(int i=0; i<2*N-1; i++) cout << node[i] << " ";
cout << endl;
for(int i=0; i<2*N-1; i++) cout << lazy[i] << " ";
cout << endl;
}
};
int N,Q;
vector<pair<int,LL>> edge[200000];
LL all = 0;
LL ans[200001];
bool visit[200000] = {};
int par[200000] = {};
int parCost[200000] = {};
int pos[200000] = {};
int c;
LL sum;
void dfs(int now, LL cost, int bef){
visit[now] = true;
par[c] = bef;
int dfs_order = c;
c++;
for(int i=0; i<edge[now].size(); i++){
if(visit[edge[now][i].first]) continue;
sum += edge[now][i].second;
parCost[c] = edge[now][i].second;
dfs(edge[now][i].first, cost + edge[now][i].second, dfs_order);
}
}
LL minimum = LLONG_MAX;
int p = -1;
void dfs2(int now, LL cost){
for(int i=0; i<edge[now].size(); i++){
if(visit[edge[now][i].first]) cost += edge[now][i].second;
}
if(minimum > cost){
minimum = cost;
p = now;
}
visit[now] = true;
c++;
for(int i=0; i<edge[now].size(); i++){
if(visit[edge[now][i].first]) continue;
cost -= edge[now][i].second;
dfs2(edge[now][i].first, cost);
cost += edge[now][i].second;
}
}
int main(){
scanf("%d", &N);
for(int i=0; i<N-1; i++){
int A,B,C,D;
scanf("%d%d%d%d", &A, &B, &C, &D);
A--; B--;
edge[A].PB(MP(B,C));
edge[B].PB(MP(A,D));
all += C+D;
}
for(int i=0; i<=N; i++) ans[i] = LLONG_MAX;
//root doko
for(int j=0; j<N; j++) visit[j] = false;
c = 0;
sum = 0;
dfs(0,0, -1);
for(int j=0; j<N; j++) visit[j] = false;
c = 0;
dfs2(0,sum);
cout << minimum << endl;
return 0;
}
Compilation message
lamp.cpp: In function 'void dfs(int, long long int, int)':
lamp.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
lamp.cpp: In function 'void dfs2(int, long long int)':
lamp.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
lamp.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
lamp.cpp: In function 'int main()':
lamp.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
lamp.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &A, &B, &C, &D);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
