oj.uz

답안 #1046164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046164 2024-08-06T10:50:04 Z VahanAbraham Petrol stations (CEOI24_stations) C++17
0 / 100
 1 ms 2652 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 70005;
const ll oo = 100000000000000000, MOD = 1000000007;


ll cnt[N], ans[N], pat[N];
int n, k, sz[N], a[N], last = 1;
vector<pair<int, int>> g[N];

void dfs(int u, int p) {
    //cout << u << endl;
    a[last] = u;
    ++last;
    for (int i = 0; i < g[u].size(); ++i) {
        int h = g[u][i].fr;
        int w = g[u][i].sc;
        if (h != p) {
            dfs(h, u);
        }
    }
}


void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({ v,w });
        g[v].pb({ u,w });
    }
    for (int i = 0; i < n; ++i) {
        if (g[i].size() == 1) {
            last = 1;
            dfs(i, -1);
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans[i] = 1;
        if (i - k >= 1) {
            ans[i] += ans[i - k];
        }
        pat[a[i]] += (ans[i] - 1) * (n - i + 1);
    }
    for (int i = n; i >= 1; --i) {
        ans[i] = 1;
        if (n - i >= k) {
            ans[i] += ans[i + k];
        }
        pat[a[i]] += (ans[i] - 1) * (i);
    }
    for (int i = 0; i < n; ++i) {
        cout << pat[i] << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < g[u].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:62:13: warning: unused variable 'w' [-Wunused-variable]
   62 |         int w = g[u][i].sc;
      |             ^

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -