Submission #524563

#	Time	Username	Problem	Language	Result	Execution time	Memory
524563		mathking1021	도로 개발 (JOI15_road_development)	C++17	100 / 100	685 ms	48352 KiB

road_development

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long ll;

ll n, Q;
ll a[300005], b[300005], c[300005], d[300005];
ll cp[100005];
ll ans[300005];
vector<ll> ve[100005];
ll e[25][100005];
ll h[100005];
ll cp2[100005];
ll cnt = 1;
ll f[100005], g[100005];
ll base = 131072;
ll seg[400005];

ll fnd(ll p)
{
    if(cp[p] == p) return p;
    return cp[p] = fnd(cp[p]);
}

ll fnd2(ll p)
{
    if(cp2[p] == p) return p;
    return cp2[p] = fnd2(cp2[p]);
}

void dfs(ll p, ll q)
{
    if(e[0][p]) return;
    e[0][p] = q;
    f[p] = cnt, cnt++;
    if(p != q) h[p] = h[q] + 1;
    for(ll i = 0; i < ve[p].size(); i++)
    {
        dfs(ve[p][i], p);
    }
    g[p] = cnt - 1;
}

ll lca(ll p, ll q)
{
    if(h[p] > h[q]) swap(p, q);
    ll t1 = h[q] - h[p];
    for(ll i = 20; i >= 0; i--)
    {
        if(t1 & (1 << i)) q = e[i][q];
    }
    for(ll i = 20; i >= 0; i--)
    {
        if(e[i][p] == e[i][q]) continue;
        p = e[i][p], q = e[i][q];
    }
    if(p != q) p = e[0][p], q = e[0][q];
    return p;
}

void upd2(ll p, ll q)
{
    p += base;
    while(p >= 1)
    {
        seg[p] += q;
        p /= 2;
    }
}

void upd(ll p)
{
    ll t1 = f[p];
    ll t2 = g[p];
    t2++;
    upd2(t1, -1);
    upd2(t2, 1);
}

ll que(ll p, ll q)
{
//    p = f[p];
    q = f[q];
    p += base;
    q += base;
    ll re = 0;
    while(p < q)
    {
        if(p % 2 == 1) re += seg[p], p++;
        if(q % 2 == 0) re += seg[q], q--;
        p /= 2, q /= 2;
    }
    if(p == q) re += seg[p];
    return re;
}

int main()
{
    scanf("%lld%lld", &n, &Q);
    for(ll i = 1; i <= n; i++) cp[i] = cp2[i] = i;
    for(ll i = 0; i < Q; i++)
    {
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
        if(a[i] == 1)
        {
            if(fnd(b[i]) == fnd(c[i]))
            {
                d[i] = 1;
            }
            else
            {
                cp[fnd(b[i])] = fnd(c[i]);
                ve[b[i]].push_back(c[i]);
                ve[c[i]].push_back(b[i]);
            }
        }
        else
        {
            if(fnd(b[i]) != fnd(c[i])) ans[i] = -1;
        }
    }
    for(ll i = 1; i <= n; i++)
    {
        if(e[0][i] > 0) continue;
        dfs(i, i);
    }
    for(ll i = 1; i <= n; i++)
    {
        seg[f[i] + base] += h[i];
        seg[f[i] + base + 1] -= h[i];
    }
    for(ll i = base - 1; i >= 1; i--)
    {
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    }
    for(ll i = 1; i <= 20; i++)
    {
        for(ll j = 1; j <= n; j++)
        {
            e[i][j] = e[i - 1][e[i - 1][j]];
        }
    }
    for(ll i = 0; i < Q; i++)
    {
//        ll tttttt1 = 1;
//        if(i == 1355)
//        {
//            tttttt1 = 2;
//        }
        if(a[i] == 1)
        {
            if(d[i] == 1)
            {
                ll t1 = b[i];
                ll t2 = c[i];
                ll t3 = lca(b[i], c[i]);
                t1 = fnd2(t1);
                t2 = fnd2(t2);
                while(h[t1] > h[t3])
                {
//                    if(t1 == 777) return -1;
                    upd(t1);
                    cp2[fnd2(t1)] = e[0][t1];
                    t1 = fnd2(t1);
                }
                while(h[t2] > h[t3])
                {
//                    if(t2 == 777) return -1;
                    upd(t2);
                    cp2[fnd2(t2)] = e[0][t2];
                    t2 = fnd2(t2);
                }
            }
        }
        else
        {
            if(ans[i] != -1)
            {
                ll t1 = b[i];
                ll t2 = c[i];
                ll t3 = lca(b[i], c[i]);
                ll t6 = que(0, t1);
                ll t4 = que(0, t1) - que(0, t3);
                ll t5 = que(0, t2) - que(0, t3);
//                if(i == 1408) printf("%lld %lld %lld %lld %lld %lld\n", t1, t2, t3, t4, t5, t6);
                ans[i] = t4 + t5;
            }
        }
    }
    for(ll i = 0; i < Q; i++)
    {
        if(a[i] == 2)
        {
//            printf("%lld %lld\n", ans[i], i);
            printf("%lld\n", ans[i]);
        }
    }
    return 0;
}

Compilation message (stderr)

road_development.cpp: In function 'void dfs(ll, ll)':
road_development.cpp:39:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(ll i = 0; i < ve[p].size(); i++)
      |                   ~~^~~~~~~~~~~~~~
road_development.cpp: In function 'int main()':
road_development.cpp:184:20: warning: unused variable 't6' [-Wunused-variable]
  184 |                 ll t6 = que(0, t1);
      |                    ^~
road_development.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%lld%lld", &n, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
road_development.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15