Submission #385251

#	Time	Username	Problem	Language	Result	Execution time	Memory
385251		ivan24	Dreaming (IOI13_dreaming)	C++14	100 / 100	228 ms	32716 KiB

dreaming

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

using ll = int;
using namespace std;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
const ll INF = 1e9;

#define S second
#define F first

class SmallTree{
private:
    vvii adjList;
    ll root,n,maxDist,diam;
    vi heights;

    ll findMaxDist (ll curRt){
        queue<ll> q;
        vi dist;
        dist.assign(n,INF);
        dist[curRt] = 0;
        q.push(curRt);

        ll res = 0;

        while (!q.empty()){
            ll v = q.front();
            q.pop();
            for (auto e: adjList[v]){
                if (dist[e.S] == INF){
                    dist[e.S] = dist[v]+e.F;
                    res = max(res,dist[e.S]);
                    q.push(e.S);
                }
            }
        }
        return res;
    }

    void findRoot(){
        // slow step
        priority_queue<ii> pq;
        vector<set<ii> > adjSet;
        adjSet.resize(n);
        for (ll i = 0; n > i; i++){
            for (auto e: adjList[i]){
                adjSet[i].insert(e);
            }
        }

        vi deg, dist;
        deg.resize(n);
        dist.assign(n,0);
        for (ll i = 0; n > i; i++){
            deg[i] = adjList[i].size();
            if (deg[i] == 1){
                pq.emplace(0,i);
            }
        }

        while (!pq.empty()){
            ii te = pq.top();
            pq.pop();

            ll w = -te.F;
            ll v = te.S;

            //cout << v << ' ' << w << endl;

            for (auto e: adjSet[v]){
                dist[e.S] = max(dist[e.S], w+e.F);
                adjSet[e.S].erase(ii(e.F,v));
                deg[e.S]--;
                if (deg[e.S] == 1){
                    pq.emplace(-dist[e.S],e.S);
                }
            }
        }

        maxDist = -1;
        for (ll i = 0; n > i; i++){
            if (dist[i] > maxDist){
                root = i;
                maxDist = dist[i];
            }
        }

    }

    ll findHeight (ll p, ll v){
        heights[v] = 0;
        for (auto e: adjList[v]){
            if (e.S == p) continue;
            heights[v] = max(heights[v],findHeight(v,e.S)+e.F);
        }
        return heights[v];
    }

    void findDiam (){
        heights.resize(n);
        findHeight(-1,root);

        vi dists;
        for (auto e: adjList[root]){
            dists.push_back(e.F+heights[e.S]);
        }

        sort(dists.begin(),dists.end());
        reverse(dists.begin(),dists.end());

        diam = 0;
        for (ll i = 0; 2 > i && dists.size() > i; i++){
            diam += dists[i];
        }

    }
public:
    SmallTree(const vvii& _adjList): adjList(_adjList){
        n = adjList.size();
        findRoot();
        findDiam();
    }
    ll getMaxDist(){
        return maxDist;
    }
    ll getDiam(){
        return diam;
    }
    SmallTree(){}
};

class UnionFind{
private:
    ll n;
    vi sz, p;
public:
    UnionFind(ll n): n(n), sz(n,1), p(n){
        for (ll i = 0; n > i; i++) p[i] = i;
    }
    ll root(ll x){
        if (p[x] != x) p[x] = root(p[x]);
        return p[x];
    }
    void unify (ll x, ll y){
        //cout <<"unify: " << x << " " << y << endl;
        x = root(x), y = root(y);
        if (x == y) return;

        if (sz[x] > sz[y]) swap(x,y);
        p[x] = y;
        sz[y] += sz[x];
    }
    vvi get_ccs(){
        vvi te;
        te.resize(n);
        for (ll i = 0; n > i; i++){
            te[root(i)].push_back(i);
        }
        vvi res;
        for (ll i = 0; n > i; i++){
            if (te[i].size() > 0) res.push_back(te[i]);
        }
        return res;
    }
};

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    UnionFind uf(n);
    for (ll i = 0; m > i; i++){
        uf.unify(a[i], b[i]);
    }
    vvi ccs = uf.get_ccs();
    vii encoding(n);
    for (ll i = 0; ccs.size() > i; i++){
        for (ll j = 0; ccs[i].size() > j ;j++){
            encoding[ccs[i][j]] = ii(i,j);
        }
    }
    vector<vvii> adjLists;
    adjLists.resize(ccs.size());
    for (ll i = 0; ccs.size() > i; i++){
        adjLists[i].resize(ccs[i].size());
    }

    for (ll i = 0; m > i; i++){
        ii code = encoding[a[i]];
        adjLists[code.F][code.S].emplace_back(t[i],encoding[b[i]].S);
        code = encoding[b[i]];
        adjLists[code.F][code.S].emplace_back(t[i],encoding[a[i]].S);
    }

    /*

    for (auto i: ccs){
        cout << "cc: \n";
        for (auto j: i){
            cout << j << ' ';
        }
        cout << endl;
    }
    for (auto i: adjLists){
        cout << "adjList: \n";
        for (ll j = 0; i.size() > j; j++){
            cout << j << ": ";
            for (auto p: i[j]) cout << "(" << p.F << " , " << p.S << "), ";
            cout << endl;
        }

    }
    */

    vector<SmallTree> smallTrees;
    smallTrees.resize(adjLists.size());
    for (ll i = 0; adjLists.size() > i; i++){
        smallTrees[i] = SmallTree(adjLists[i]);
    }
    /*
    cout << "maxDists: ";
    for (auto i: smallTrees){
        cout << i.getMaxDist() << ' ';
    }
    cout << endl;
    cout << "diams: ";
    for (auto i: smallTrees){
        cout << i.getDiam() << ' ';
    }
    cout << endl;
    */

    ll res = 0;
    for (auto i: smallTrees){
        res = max(res,i.getDiam());
    }
    vi maxDists; maxDists.resize(smallTrees.size());
    for (ll i = 0; smallTrees.size() > i; i++){
        maxDists[i] = smallTrees[i].getMaxDist();
    }
    sort(maxDists.begin(),maxDists.end());
    reverse(maxDists.begin(),maxDists.end());

    if (maxDists.size() >= 2){
        ll te = l;
        for (ll i = 0; 2 > i && maxDists.size() > i; i++){
            te += maxDists[i];
        }
        res = max(te,res);
    }
    if (maxDists.size() >= 3){
        ll te = 2*l;
        for (ll i = 1; 3 > i && maxDists.size() > i; i++)
            te += maxDists[i];
        res = max(te,res);
    }

    return res;



}

/*


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {
	int N, M, L, i;
	int res;

	FILE *f = fopen("dreaming.in", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d%d%d", &N, &M, &L);
	for (i = 0; i < M; i++)
		res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
	fclose(f);

	int answer = travelTime(N, M, L, A, B, T);
	printf("%d\n", answer);

	return 0;
}

*/

Compilation message (stderr)

dreaming.cpp: In member function 'void SmallTree::findDiam()':
dreaming.cpp:117:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  117 |         for (ll i = 0; 2 > i && dists.size() > i; i++){
      |                                 ~~~~~~~~~~~~~^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:179:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  179 |     for (ll i = 0; ccs.size() > i; i++){
      |                    ~~~~~~~~~~~^~~
dreaming.cpp:180:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  180 |         for (ll j = 0; ccs[i].size() > j ;j++){
      |                        ~~~~~~~~~~~~~~^~~
dreaming.cpp:186:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  186 |     for (ll i = 0; ccs.size() > i; i++){
      |                    ~~~~~~~~~~~^~~
dreaming.cpp:219:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  219 |     for (ll i = 0; adjLists.size() > i; i++){
      |                    ~~~~~~~~~~~~~~~~^~~
dreaming.cpp:240:38: warning: comparison of integer expressions of different signedness: 'std::vector<SmallTree>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  240 |     for (ll i = 0; smallTrees.size() > i; i++){
      |                    ~~~~~~~~~~~~~~~~~~^~~
dreaming.cpp:248:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  248 |         for (ll i = 0; 2 > i && maxDists.size() > i; i++){
      |                                 ~~~~~~~~~~~~~~~~^~~
dreaming.cpp:255:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  255 |         for (ll i = 1; 3 > i && maxDists.size() > i; i++)
      |                                 ~~~~~~~~~~~~~~~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23