Submission #197274

#	Time	Username	Problem	Language	Result	Execution time	Memory
197274		stefdasca	Untitled (POI11_ins)	C++14	100 / 100	1494 ms	106020 KiB

Main

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, sts[1000002];

vector<int> v[1000002];

vector<pair<int, int> > centri;

void dfs(int dad, int nod)
{
    sts[nod] = 1;
    int mx = 0;
    int wh = 0;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfs(nod, vecin);
        sts[nod] += sts[vecin];
        if(sts[vecin] > mx)
        {
            mx = sts[vecin];
            wh = vecin;
        }
    }
    if(n - sts[nod] >= mx)
        mx = n - sts[nod], wh = dad;
    if(mx <= (n-1) / 2 + (n-1) % 2)
    {
        if(n % 2 == 0 && mx == (n-1) / 2 + (n-1) % 2)
            centri.pb({nod, wh});
        else
            centri.pb({nod, 0});
    }
}

ll ans[1000002];
int dist[1000002];

bool viz[1000002];
void bfs(int src, int org)
{
    for(int i = 1; i <= n; ++i)
        viz[i] = 0, dist[i] = 0;
    deque<pair<int, int> > d;
    d.pb({src, 1});
    viz[src] = 1;
    int mx = 0;
    while(!d.empty())
    {
        int nod = d[0].fi;
        int ax = d[0].se;
        if(d[0].se)
            mx = max(mx, dist[nod]);
        d.pop_front();
        viz[nod] = 1;
        ans[src] = ans[src] + 2 * dist[nod];
        if(nod == src && org != 0)
        {
            for(int i = 0; i < v[nod].size(); ++i)
            {
                int vecin = v[nod][i];
                if(viz[vecin])
                    continue;
                dist[vecin] = dist[nod] + 1;
                d.pb({vecin, (vecin == org)});
            }
        }
        else
        {
            for(int i = 0; i < v[nod].size(); ++i)
            {
                int vecin = v[nod][i];
                if(viz[vecin])
                    continue;
                dist[vecin] = dist[nod] + 1;
                d.pb({vecin, ax});
            }
        }
    }
    ans[src] -= mx;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(0, 1);
    for(int i = 1; i <= n; ++i)
        ans[i] = -1;
    for(int i = 0; i < centri.size(); ++i)
        ans[centri[i].fi] = 0, bfs(centri[i].fi, centri[i].se);
    for(int i = 1; i <= n; ++i)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

ins.cpp: In function 'void dfs(int, int)':
ins.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
ins.cpp: In function 'void bfs(int, int)':
ins.cpp:76:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[nod].size(); ++i)
                            ~~^~~~~~~~~~~~~~~
ins.cpp:87:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[nod].size(); ++i)
                            ~~^~~~~~~~~~~~~~~
ins.cpp: In function 'int main()':
ins.cpp:121:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < centri.size(); ++i)
                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10