oj.uz

Submission #786338

# Submission time Handle Problem Language Result Execution time Memory
786338 2023-07-18T06:43:52 Z 반딧불(#10026) Paths (RMI21_paths) C++17
12 / 100
 149 ms 32452 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int s, e; ll v; int idx;
    Edge(){}
    Edge(int s, int e, ll v): s(s), e(e), v(v){}
    bool operator<(const Edge &r)const{
        return idx<r.idx;
    }
};

int n, k;
Edge arr[200002];
vector<Edge> link[100002];
int in[100002], out[100002], inCnt;

void dfs_in(int x, int p=-1){
    in[x] = ++inCnt;
    for(auto y: link[x]){
        if(y.e == p) continue;
        dfs_in(y.e, x);
    }
    out[x] = inCnt;
}

vector<Edge> linkSet[100002];
ll MX[200002]; /// �� ���� �������� ���� �� �ִ밡 ���ΰ�
vector<pair<ll, ll> > options[100002]; /// �� �������� ���� �� �ִ� ��� �ɼ�

ll dfs_getValues(int x, int p=-1){
//    printf("Get value %d %d\n", x, p);
    if(!linkSet[x].empty()){
        vector<Edge> tlst;
        for(Edge y: linkSet[x]){
            if((y.idx ^ p) == 1){
                tlst.push_back(y);
                continue;
            }
            options[x].push_back(make_pair(MX[y.idx] = (dfs_getValues(y.e, y.idx) + y.v), y.idx));
        }
        linkSet[x].swap(tlst);
        sort(options[x].begin(), options[x].end());
        options[x].erase(unique(options[x].begin(), options[x].end()), options[x].end());
        reverse(options[x].begin(), options[x].end());
    }
    if(options[x].empty()) return 0;
    else if((options[x][0].second ^ p) != 1) return options[x][0].first;
    else if((int)options[x].size() == 1) return 0;
    else return options[x][1].first;
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<n; i++){
        scanf("%d %d %lld", &arr[i*2-2].s, &arr[i*2-2].e, &arr[i*2-2].v);
        arr[i*2-1].s = arr[i*2-2].e, arr[i*2-1].e = arr[i*2-2].s, arr[i*2-1].v = arr[i*2-2].v;
        arr[i*2-2].idx = i*2-2, arr[i*2-1].idx = i*2-1;
        link[arr[i*2-2].s].push_back(arr[i*2-2]);
        link[arr[i*2-1].s].push_back(arr[i*2-1]);
    }
    for(int i=1; i<=n; i++) linkSet[i] = link[i];

    dfs_in(1);
    for(int i=0; i<(n-1)*2; i++){
        MX[i] = dfs_getValues(arr[i].e, i) + arr[i].v;
    }

    for(int i=1; i<=n; i++){
        ll ans = 0;
        for(Edge &p: link[i]) ans = max(ans, MX[p.idx]);
        printf("%lld\n", ans);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d %lld", &arr[i*2-2].s, &arr[i*2-2].e, &arr[i*2-2].v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 28776 KB Output is correct
2 Correct 147 ms 32452 KB Output is correct
3 Correct 107 ms 30400 KB Output is correct
4 Correct 129 ms 30384 KB Output is correct
5 Correct 136 ms 32236 KB Output is correct
6 Correct 149 ms 30052 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -