| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 518596 | blue | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "traffic.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
set<int>* neighbors;
struct compare
{
bool operator () (int c1, int c2)
{
if(neighbors[c1].size() == neighbors[c2].size()) return c1 < c2;
else return neighbors[c1].size() < neighbors[c2].size();
}
};
int LocateCenter(int N, int* P, int* A, int* B)
{
int Q = 0; //total population
for(int i = 0; i < N; i++) Q += P[i];
vector<int> S[N]; // list of stress
set<int> ne[N];
neighbors = &(ne[0]); //set of neighbors
for(int i = 0; i < N-1; i++)
{
neighbors[A[i]].insert(B[i]);
neighbors[B[i]].insert(A[i]);
}
set<int, compare> C; //set of cities
for(int i = 0; i < N; i++) C.insert(i);
int res = 2000000001; //final result
int k = 0, p, r; // smallest set element, total stress, temporary result
int t; //temp
int city;
while(C.size() > 1)
{
k = *C.begin();
C.erase(k);
p = r = 0;
for(int i = 0; i < S[k].size(); i++)
{
p += S[k][i];
r = max(r, S[k][i]);
}
if(max(r, Q - P[k] - p) <= res)
{
city = k;
res = max(r, Q - P[k] - p);
}
t = *(neighbors[k].begin());
C.erase(t);
neighbors[t].erase(k);
C.insert(t);
S[*neighbors[k].begin()].push_back(p + P[k]);
}
p = r = 0;
k = *C.begin();
for(int i = 0; i < S[k].size(); i++)
{
r = max(r, S[k][i]);
p += S[k][i];
}
r = max(r, Q - P[k] - p);
if(r < res)
{
res = r;
city = k;
}
return city;
}
// int main()
// {
// int N;
// cin >> N;
//
// int *P = new int[N], *A = new int[N-1], *B = new int[N-1];
// for(int i = 0; i < N; i++) cin >> P[i];
// for(int i = 0; i < N-1; i++) cin >> A[i] >> B[i];
//
// cout << LocateCenter(N, P, A, B) << '\n';
// return 0;
// }