oj.uz

답안 #1046091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046091 2024-08-06T09:58:02 Z SamAnd Petrol stations (CEOI24_stations) C++17
8 / 100
 404 ms 25344 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 70004;

int n;
ll k;
vector<pair<int, ll> > g[N];

bool c[N];
int q[N];
void dfs0(int x, int p)
{
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
            continue;
        if (c[h])
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }
}

int dfsc(int x, int p, int xx)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
            continue;
        if (c[h])
            continue;
        if (q[h] > q[xx] / 2)
            return dfsc(h, x, xx);
    }
    return x;
}

ll ans[N];

const int m = 17;
int pp[N][m];
ll ss[N][m];
void dfs1(int x, int p, ll dp)
{
    pp[x][0] = p;
    ss[x][0] = dp;
    for (int i = 1; i < m; ++i)
    {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
        ss[x][i] = ss[x][i - 1] + ss[pp[x][i - 1]][i - 1];
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        ll d = g[x][i].se;
        if (h == p)
            continue;
        if (c[h])
            continue;
        dfs1(h, x, d);
    }
}

int FU(int x)
{
    ll s = 0;
    for (int i = m - 1; i >= 0; --i)
    {
        if (s + ss[x][i] <= k)
        {
            s += ss[x][i];
            x = pp[x][i];
        }
    }
    return x;
}

void dfst(int x, int p, vector<int>& v)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
            continue;
        if (c[h])
            continue;
        dfst(h, x, v);
    }
    v.push_back(x);
}

int hav[N];

void ubd(vector<int>& t, int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[pos] += y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(t, tl, m, x, y, pos * 2);
    else
        ubd(t, m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = t[pos * 2] + t[pos * 2 + 1];
}

int qry(vector<int>& t, int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return (qry(t, tl, m, l, min(m, r), pos * 2) +
            qry(t, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

void solvv(int r)
{
    dfs0(r, r);
    dfs1(r, r, 0);
    map<int, vector<pair<ll, int> > > mp;
    for (int i = 0; i < g[r].size(); ++i)
    {
        int x = g[r][i].fi;
        int cx = x;
        if (c[x])
            continue;
        vector<int> v;
        dfst(x, r, v);
        for (int i = 0; i < sz(v); ++i)
            hav[v[i]] = 1;
        for (int i = 0; i < sz(v); ++i)
        {
            int x = v[i];
            int y = FU(x);
            if (y == r)
            {
                mp[cx].push_back(m_p(ss[x][m - 1], hav[x]));
            }
            else
            {
                ans[y] += hav[x] * 1LL * (q[r] - sz(v));
                hav[y] += hav[x];
            }
        }
    }

    vector<ll> xt;
    for (auto it = mp.begin(); it != mp.end(); ++it)
    {
        for (int i = 0; i < sz(it->se); ++i)
        {
            xt.push_back(it->se[i].fi);
        }
    }
    sort(all(xt));

    vector<int> t(sz(xt) * 4 + 10, 0);
    for (auto it = mp.begin(); it != mp.end(); ++it)
    {
        for (int i = 0; i < sz(it->se); ++i)
        {
            ubd(t, 1, sz(xt), lower_bound(all(xt), it->se[i].fi) - xt.begin() + 1, it->se[i].se, 1);
        }
    }

    for (int i = 0; i < g[r].size(); ++i)
    {
        int x = g[r][i].fi;
        if (c[x])
            continue;
        vector<int> v;
        dfst(x, r, v);
        reverse(all(v));
        for (int i = 0; i < sz(mp[x]); ++i)
        {
            ubd(t, 1, sz(xt), lower_bound(all(xt), mp[x][i].fi) - xt.begin() + 1, -mp[x][i].se, 1);
        }
        for (int i = 0; i < sz(v); ++i)
            hav[v[i]] = 0;
        hav[r] = 1;
        for (int i = 0; i < sz(v); ++i)
        {
            int x = v[i];
            ll r = k - ss[pp[x][0]][m - 1];
            ll l = k - ss[x][m - 1] + 1;
            if (l <= r)
            {
                int l2 = lower_bound(all(xt), l) - xt.begin() + 1;
                int r2 = upper_bound(all(xt), r) - xt.begin();
                if (l2 <= r2)
                {
                    assert(1 <= l2 && r2 <= sz(xt));
                    ans[pp[x][0]] += qry(t, 1, sz(xt), l2, r2, 1) * 1LL * q[x];
                    hav[pp[x][0]] += qry(t, 1, sz(xt), l2, r2, 1);
                }
            }
            if (ss[x][m - 1] > k)
            {
                int y = pp[FU(x)][0];
                ans[pp[x][0]] += hav[y] * 1LL * q[x];
                hav[pp[x][0]] += hav[y];
            }
        }
        for (int i = 0; i < sz(mp[x]); ++i)
        {
            ubd(t, 1, sz(xt), lower_bound(all(xt), mp[x][i].fi) - xt.begin() + 1, mp[x][i].se, 1);
        }
    }
}

void solv()
{
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        ++x;
        ++y;
        g[x].push_back(m_p(y, z));
        g[y].push_back(m_p(x, z));
    }

    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        dfs0(x, x);
        x = dfsc(x, x, x);

        solvv(x);

        c[x] = true;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i].fi;
            if (!c[h])
                q.push(h);
        }
    }

    for (int x = 1; x <= n; ++x)
        cout << ans[x] << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs0(int, int)':
Main.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'int dfsc(int, int, int)':
Main.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(int, int, ll)':
Main.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfst(int, int, std::vector<int>&)':
Main.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void solvv(int)':
Main.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0; i < g[r].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int i = 0; i < g[r].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void solv()':
Main.cpp:251:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for (int i = 0; i < g[x].size(); ++i)
      |                         ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct

Subtask #1
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 6944 KB Output is correct
5 Incorrect 3 ms 8796 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 346 ms 25344 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 346 ms 25344 KB Output is correct
5 Incorrect 404 ms 25112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Incorrect 300 ms 21344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Incorrect 300 ms 21344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 6944 KB Output is correct
5 Incorrect 3 ms 8796 KB Output isn't correct
6 Halted 0 ms 0 KB -