oj.uz

답안 #197274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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