제출 #92772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92772		SamAnd	관광지 (IZhO14_shymbulak)	C++17	100 / 100	173 ms	23544 KiB

shymbulak

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define m_p make_pair
const int N = 200005;

int n;
vector<int> a[N];
pair<int, int> b[N];

int pp[N];
int ss, ff;
int c[N];

bool dfs(int x, int p)
{
    c[x] = 1;
    pp[x] = p;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        if (c[h] == 1)
        {
            ss = h;
            ff = x;
            return true;
        }
        if (c[h] == 0)
            if (dfs(h, x))
                return true;
    }
    c[x] = 2;
    return false;
}

vector<int> v;
void pre()
{
    dfs(1, 0);
    for (int x = ff; x != ss; x = pp[x])
        v.push_back(x);
    v.push_back(ss);

    for (int i = 1; i <= n; ++i)
        c[i] = 0;
    for (int i = 0; i < v.size(); ++i)
        c[v[i]] = 1;
}

int d[N];

void dfs1(int x, int p)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h] == 1)
            continue;
        d[h] = d[x] + 1;
        dfs1(h, x);
    }
}

int dans[N];
long long ans[N];

int maxu[N];
long long q[N];

void dfs2(int x, int p)
{
    bool zz = false;
    int maxu1 = d[x], maxu2 = 0;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h] == 1)
            continue;
        zz = true;
        dfs2(h, x);
        if (maxu[h] > maxu1)
        {
            maxu2 = maxu1;
            maxu1 = maxu[h];
        }
        else if (maxu[h] > maxu2)
            maxu2 = maxu[h];
    }
    if (!zz)
    {
        maxu[x] = d[x];
        q[x] = 1;
        dans[x] = 0;
        ans[x] = 1;
        return;
    }
    dans[x] = maxu1 + maxu2 - 2 * d[x];
    if (maxu1 != maxu2)
    {
        long long q1 = 0, q2 = 0;
        if (d[x] == maxu1)
            ++q1;
        if (d[x] == maxu2)
            ++q2;
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i];
            if (h == p || c[h] == 1)
                continue;
            if (maxu[h] == maxu1)
                q1 += q[h];
            if (maxu[h] == maxu2)
                q2 += q[h];
        }
        ans[x] = q1 * q2;
        maxu[x] = maxu1;
        q[x] = q1;
    }
    else
    {
        long long qm = 0;
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i];
            if (h == p || c[h] == 1)
                continue;
            if (maxu[h] == maxu1)
                qm += q[h];
        }
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i];
            if (h == p || c[h] == 1)
                continue;
            if (maxu[h] == maxu1)
                ans[x] += ((qm - q[h]) * q[h]);
        }
        ans[x] /= 2;
        maxu[x] = maxu1;
        q[x] = qm;
    }
    int maxud = dans[x];
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h] == 1)
            continue;
        maxud = max(maxud, dans[h]);
    }
    if (dans[x] != maxud)
    {
        dans[x] = maxud;
        ans[x] = 0;
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h] == 1)
            continue;
        if (dans[h] == dans[x])
            ans[x] += ans[h];
    }
}

struct ban
{
    int maxu;
    long long q;
    int laz;
    ban(){}
    ban(int maxu, long long q)
    {
        this->maxu = maxu;
        this->q = q;
        laz = 0;
    }
};

ban t[N * 4];

void shi(int pos)
{
    if (t[pos].laz == 0)
        return;
    t[pos * 2].maxu += t[pos].laz;
    t[pos * 2 + 1].maxu += t[pos].laz;
    t[pos * 2].laz += t[pos].laz;
    t[pos * 2 + 1].laz += t[pos].laz;
    t[pos].laz = 0;
}

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (l.maxu > r.maxu)
        res = l;
    else if (l.maxu < r.maxu)
        res = r;
    else
    {
        res.maxu = l.maxu;
        res.q = l.q + r.q;
    }
    res.laz = 0;
    return res;
}

void bil(int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos].maxu = maxu[v[tl]] + min(tl, (int)v.size() - tl);
        t[pos].q = q[v[tl]];
        t[pos].laz = 0;
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos].maxu += y;
        t[pos].laz += y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    if (r <= m)
        ubd(tl, m, l, r, y, pos * 2);
    else if (l > m)
        ubd(m + 1, tr, l, r, y, pos * 2 + 1);
    else
    {
        ubd(tl, m, l, m, y, pos * 2);
        ubd(m + 1, tr, m + 1, r, y, pos * 2 + 1);
    }
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

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

int vdans[N];
long long vans[N];

void vqry(int i)
{
    int u = (v.size() - 1) / 2;
    if (v.size() % 2 == 1)
    {
        ban ll;
        int l = i + 1, r = i + u;
        if (l >= v.size() && r >= v.size())
        {
            l -= v.size();
            r -= v.size();
        }
        if (r < v.size())
            ll = qry(0, v.size() - 1, l, r, 1);
        else
        {
            ll = mer(qry(0, v.size() - 1, l, v.size() - 1, 1), qry(0, v.size() - 1, 0, r - v.size(), 1));
        }
        ban rr;
        l = i - u, r = i - 1;
        if (l < 0 && r < 0)
        {
            l += v.size();
            r += v.size();
        }
        if (l >= 0)
            rr = qry(0, v.size() - 1, l, r, 1);
        else
        {
            rr = mer(qry(0, v.size() - 1, 0, r, 1), qry(0, v.size() - 1, l + v.size(), v.size() - 1, 1));
        }
        ban res = mer(ll, rr);
        vans[i] = res.q * q[v[i]];
        vdans[i] = res.maxu + maxu[v[i]];
    }
    else
    {
        ban ll;
        int l = i + 1, r = i + u;
        if (l >= v.size() && r >= v.size())
        {
            l -= v.size();
            r -= v.size();
        }
        if (r < v.size())
            ll = qry(0, v.size() - 1, l, r, 1);
        else
        {
            ll = mer(qry(0, v.size() - 1, l, v.size() - 1, 1), qry(0, v.size() - 1, 0, r - v.size(), 1));
        }
        ban rr;
        l = i - u, r = i - 1;
        if (l < 0 && r < 0)
        {
            l += v.size();
            r += v.size();
        }
        if (l >= 0)
            rr = qry(0, v.size() - 1, l, r, 1);
        else
        {
            rr = mer(qry(0, v.size() - 1, 0, r, 1), qry(0, v.size() - 1, l + v.size(), v.size() - 1, 1));
        }
        ban res = mer(ll, rr);
        res = mer(res, ban(maxu[v[(i + u + 1) % v.size()]] + u + 1, q[v[(i + u + 1) % v.size()]] * 2));
        vans[i] = res.q * q[v[i]];
        vdans[i] = res.maxu + maxu[v[i]];
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("shymbulak.in", "r", stdin);
    //freopen("shymbulak.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
        b[i] = m_p(x, y);
    }
    pre();
    for (int i = 0; i < v.size(); ++i)
    {
        //cout << v[i] << ' ';
        dfs1(v[i], 0);
        dfs2(v[i], 0);
    }
    //cout << endl;

    /*for (int i = 0; i < v.size(); ++i)
    {
        for (int j = 0; j < v.size(); ++j)
        {
            if (j == i)
                continue;
            if (maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i)) > vdans[i])
            {
                vdans[i] = maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i));
                if (abs(j - i) ==  v.size() - abs(j - i))
                    vans[i] = q[v[j]] * 2;
                else
                    vans[i] = q[v[j]];
            }
            else if (maxu[v[j]] + min(abs(j - i), (int)v.size() - abs(j - i)) == vdans[i])
            {
                if (abs(j - i) ==  v.size() - abs(j - i))
                    vans[i] += q[v[j]] * 2;
                else
                    vans[i] += q[v[j]];
            }
        }
        vdans[i] += maxu[v[i]];
        vans[i] *= q[v[i]];
    }*/

    bil(0, v.size() - 1, 1);
    vqry(0);
    for (int i = 1; i < v.size(); ++i)
    {
        int u = v.size() / 2;
        int l = i, r = i + u - 1;
        if (l >= v.size() && r >= v.size())
        {
            l -= v.size();
            r -= v.size();
        }
        if (r < v.size())
            ubd(0, v.size() - 1, l, r, -1, 1);
        else
        {
            ubd(0, v.size() - 1, l, v.size() - 1, -1, 1);
            ubd(0, v.size() - 1, 0, r - v.size(), -1, 1);
        }
        l = i - u, r = i - 1;
        if (l < 0 && r < 0)
        {
            l += v.size();
            r += v.size();
        }
        if (l >= 0)
            ubd(0, v.size() - 1, l, r, 1, 1);
        else
        {
            ubd(0, v.size() - 1, 0, r, 1, 1);
            ubd(0, v.size() - 1, l + v.size(), v.size() - 1, 1, 1);
        }
        vqry(i);
    }

    int maxuu = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        //cout << vdans[i] << ' ';
        maxuu = max(maxuu, dans[v[i]]);
        maxuu = max(maxuu, vdans[i]);
    }
    //cout << endl;

    long long yans = 0, yyans = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        if (dans[v[i]] == maxuu)
            yans += ans[v[i]];
        if (vdans[i] == maxuu)
            yyans += vans[i];
    }
    cout << yans + yyans / 2 << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'bool dfs(int, int)':
shymbulak.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void pre()':
shymbulak.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(int, int)':
shymbulak.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
shymbulak.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
shymbulak.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
shymbulak.cpp:134:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
shymbulak.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
shymbulak.cpp:159:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void vqry(int)':
shymbulak.cpp:276:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
             ~~^~~~~~~~~~~
shymbulak.cpp:276:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
                              ~~^~~~~~~~~~~
shymbulak.cpp:281:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < v.size())
             ~~^~~~~~~~~~
shymbulak.cpp:308:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
             ~~^~~~~~~~~~~
shymbulak.cpp:308:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
                              ~~^~~~~~~~~~~
shymbulak.cpp:313:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < v.size())
             ~~^~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:354:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shymbulak.cpp:390:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shymbulak.cpp:394:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
             ~~^~~~~~~~~~~
shymbulak.cpp:394:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l >= v.size() && r >= v.size())
                              ~~^~~~~~~~~~~
shymbulak.cpp:399:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < v.size())
             ~~^~~~~~~~~~
shymbulak.cpp:423:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shymbulak.cpp:432:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shymbulak.cpp:344:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shymbulak.cpp:348:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50