Submission #584689

#	Time	Username	Problem	Language	Result	Execution time	Memory
584689		teki	Traffic (IOI10_traffic)	C++11	100 / 100	1633 ms	172524 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
const ll MN = 100000000000007;

using namespace std;

int LocateCentre(int n, int lugje[], int edPrv[], int edVtor[]) {
    set<int> pat[n+5];
    for (int i = 0; i<n-1; i++) {
        pat[edPrv[i]].insert(edVtor[i]);
        pat[edVtor[i]].insert(edPrv[i]);
    }

    priority_queue<pair<int,int>> pq;
    for (int i = 0; i<n; i++) if (pat[i].size() == 1) pq.push({-lugje[i],i});

    int res = 0;

    while (!pq.empty()) {
        int broj = pq.top().first, i = pq.top().second;
        res = i;

        pq.pop();

        int sled = *pat[i].begin();

        lugje[sled] += lugje[i];
        pat[i].erase(sled);
        pat[sled].erase(i);

        if (pat[sled].size() == 1) pq.push({-lugje[sled],sled});
    }

    return res;
}

//int main()
//{
//    #if LOCAL_DEBUG
//        fstream cin("in.txt");
//    #endif
//
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
//
//
//
//    return 0;
//}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:25:13: warning: unused variable 'broj' [-Wunused-variable]
   25 |         int broj = pq.top().first, i = pq.top().second;
      |             ^~~~

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