제출 #964352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964352		anango	Traffic (IOI10_traffic)	C++17	100 / 100	854 ms	174560 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> sos;
vector<vector<int>> adjlist;
vector<int> sizes;
vector<int> parent;
void dfs(int node, int par) {
    int su=0;
    for (auto j:adjlist[node]) {
        if (j==par) {
            continue;
        }
        parent[j] = node;
        dfs(j,node);
        su+=sos[j];
    }
    su+=sizes[node];
    sos[node] = su;
}


int LocateCentre(int N, int pp[], int S[], int D[]) {

    adjlist=vector<vector<int>>(N);
    sizes=vector<int>(N);
    sos=vector<int>(N,0);
    parent=vector<int>(N,-1);
    int alls = 0;
    for (int i=0; i<N; i++) {
        sizes[i] = pp[i];
        alls+=sizes[i];
    }
    for (int i=0; i<N-1; i++) {
        adjlist[S[i]].push_back(D[i]);
        adjlist[D[i]].push_back(S[i]);
    }
    dfs(0, -1);
    for (int i=0; i<N; i++) {
        //cout << i <<" " << parent[i] << endl;
    }
    int INF=2100000000;
    int mans=INF;
    int mpos = -1;
    for (int i=0; i<N; i++) {
        int ma=0;
        int tsum=0;
        for (auto j:adjlist[i]) {
            if (j==parent[i]) {
                continue;
            }
            ma=max(ma,sos[j]);
            tsum+=sos[j];
            //cout << i <<" " <<j <<" " << sos[j] << endl;
            
        }
        tsum+=sizes[i];
        tsum=alls-tsum;
        ma=max(ma,tsum);
        //cout << i <<" " << ma << endl;
        if (ma<mans) {
            mans=ma;
            mpos=i;
        }

    }
    return mpos;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25