Submission #197274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197274	2020-01-19T20:52:20 Z	stefdasca	Inspection (POI11_ins)	C++14	100 / 100	1494 ms	106020 KB

#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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24056 KB	Output is correct
2	Correct	24 ms	23800 KB	Output is correct
3	Correct	23 ms	23800 KB	Output is correct
4	Correct	23 ms	23800 KB	Output is correct
5	Correct	30 ms	23800 KB	Output is correct
6	Correct	28 ms	23800 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23900 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	24056 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	25 ms	24056 KB	Output is correct
4	Correct	25 ms	24056 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	25084 KB	Output is correct
2	Correct	37 ms	25336 KB	Output is correct
3	Correct	37 ms	25592 KB	Output is correct
4	Correct	36 ms	25180 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	26360 KB	Output is correct
2	Correct	51 ms	26876 KB	Output is correct
3	Correct	49 ms	27256 KB	Output is correct
4	Correct	50 ms	26468 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	30388 KB	Output is correct
2	Correct	100 ms	30976 KB	Output is correct
3	Correct	101 ms	31864 KB	Output is correct
4	Correct	93 ms	30328 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	717 ms	56732 KB	Output is correct
2	Correct	681 ms	62616 KB	Output is correct
3	Correct	716 ms	68340 KB	Output is correct
4	Correct	536 ms	56420 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1482 ms	89628 KB	Output is correct
2	Correct	1406 ms	101040 KB	Output is correct
3	Correct	1378 ms	105732 KB	Output is correct
4	Correct	1084 ms	88948 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1424 ms	89576 KB	Output is correct
2	Correct	1494 ms	100624 KB	Output is correct
3	Correct	1418 ms	106020 KB	Output is correct
4	Correct	1087 ms	89084 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1421 ms	89564 KB	Output is correct
2	Correct	1420 ms	101240 KB	Output is correct
3	Correct	1352 ms	105888 KB	Output is correct
4	Correct	1105 ms	88968 KB	Output is correct