제출 #402997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402997		PedroBigMan	꿈 (IOI13_dreaming)	C++14	59 / 100	248 ms	65540 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

class WTree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<pl> > sons;
    vector<vector<pl> > adj;
    ll root;
    vector<bool> visited;
    vector<vector<ll> > farthest_dir;
    vector<ll> farthest_down;
    vector<ll> farthest_up;
    vector<ll> farthest;
	vector<ll> dist;
	pair<ll,pl> diametre;
    
    WTree(vector<vector<pl> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);}
		REP(i,0,N) {visited.pb(false);}
        DFS_Build(r,r); 
		vector<ll> xxx;
        REP(i,0,N) {farthest_up.pb(0); farthest_down.pb(0); farthest_dir.pb(xxx); farthest.pb(0);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
    }
	
	void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
        p[s]=par;
		visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i].ff==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i].ff,s);
        }
        return;
    }
	
	void DFS_distance(ll s, ll las)
    {
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i].ff==las) {continue;}
            dist[adj[s][i].ff]=dist[s]+adj[s][i].ss;
            DFS_distance(adj[s][i].ff,s);
        }
    }
    
    void distance(ll s)
    {
        dist.clear(); REP(i,0,N) {dist.pb(INF);}
        dist[s]=0LL;
        DFS_distance(s,s);
    }
    
    void Calc_Diametre()
    {
        distance(root); 
        vector<ll>::iterator it=max_element(whole(dist));
        ll ind=it-dist.begin();
        distance(ind);
        diametre.ss.ff=ind;
        it=max_element(whole(dist));
        diametre.ss.ss=it-dist.begin();
        diametre.ff=*it;
    }
    
    void Calc_farthest_down(ll s)
    {
        REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i].ff);}
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i].ff==p[s]) {continue;}
            farthest_dir[s][i]=farthest_down[adj[s][i].ff]+adj[s][i].ss;
            farthest_down[s]=max(farthest_down[s],farthest_dir[s][i]);
        }
    }
    
    void Calc_farthest_up(ll s)
    {
        if(s==root) {farthest_up[s]=0LL;}
        pl best_dis=mp(0,0);
        REP(i,0,adj[s].size()) 
        {
            if(farthest_dir[s][i]>best_dis.ff) {best_dis.ss=best_dis.ff; best_dis.ff=farthest_dir[s][i];}
            else if(farthest_dir[s][i]>best_dis.ss) {best_dis.ss=farthest_dir[s][i];}
        }
        REP(i,0,adj[s].size())
        {
            if(adj[s][i].ff==p[s]) {continue;}
            ll c = adj[s][i].ff;
            if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+adj[s][i].ss;}
            else {farthest_up[c]=best_dis.ff+adj[s][i].ss;}
            REP(j,0,adj[c].size()) {if(adj[c][j].ff==s) {farthest_dir[c][j]=farthest_up[c];}}
        }
        REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i].ff);}
    }
    
    void Calc_farthest()
    {
        Calc_farthest_down(root);
        Calc_farthest_up(root);
        REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
    }
	
	pl Radius() //returns {centre, radius}
	{
		Calc_farthest();
		ll ind=0LL; ll val = farthest[0];
		REP(i,1,N) 
		{
			if(farthest[i]<val) {val=farthest[i]; ind=i;}
		}
		return (pl) {ind,val};
	}
   	
	
};

class WG //everything works for weighted directed graphs except dynamic graph
{
    public:
    ll N; vector<vector<pl> > adj;
 	vector<bool> visited;
	vector<ll> current;
    
    WG(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
        REP(i,0,N) {visited.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
	
	void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        current.pb(s); //only needed for CC
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i].ff]) {DFS(adj[s][i].ff);}
        }
        return;
    }
	
	vector<vector<ll> > CC()
    {
        Reset();
        ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
        vector<vector<ll> > ans;
        while(missing>0)
        {
            REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
            current.clear();
            DFS(fi);
            ans.pb(current);
            missing-=current.size();
        }
        return ans;
    }
	
	vector<WTree> CCG()
    {
        Reset();
        vector<WTree> ans;
        vector<vector<ll> > CC=(*this).CC();
        unordered_map<ll,ll> m; vector<pl> xx; vector<vector<pl> > ad;
        REP(cc,0,CC.size()) 
        {
            m.clear(); 
            ad.clear(); 
            ll NN=CC[cc].size();
            REP(i,0,NN) {ad.pb(xx);}
            REP(i,0,NN) {m[CC[cc][i]]=i;}
            ll a,b;
            REP(i,0,NN)
            {
                a=CC[cc][i];
                REP(j,0,adj[a].size()) {b=adj[a][j].ff; ad[i].pb({m[b],adj[a][j].ss});}
            }
            WTree H(ad);
            ans.pb(H);
        }
        return ans;
    }
};

int travelTime(int n, int m, int L, int A[], int B[], int T[]) 
{
	int a;
    ll N = (ll) n; ll M = (ll) m; vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
	REP(i,0,M)
	{
		adj[A[i]].pb({B[i],T[i]}); adj[B[i]].pb({A[i],T[i]});
	}
	WG G(adj);
	vector<WTree> F = G.CCG();
	ll ans = 0LL;
	REP(i,0,F.size()) {F[i].Calc_Diametre(); ans=max(ans,F[i].diametre.ff);}
	vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
	sort(whole(R)); reverse(whole(R));
	if(R.size()>=2) {ans=max(ans,L+R[0]+R[1]);}
	if(R.size()>=3) {ans=max((ll) ans,(ll) 2LL*L+R[1]+R[2]);}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In constructor 'WTree::WTree(std::vector<std::vector<std::pair<int, int> > >, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   61 |         REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
      |                         ~~~~~~~~~~~~~~~~~
dreaming.cpp:61:21: note: in expansion of macro 'REP'
   61 |         REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
      |                     ^~~
dreaming.cpp: In member function 'void WTree::DFS_Build(ll, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   73 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:73:9: note: in expansion of macro 'REP'
   73 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void WTree::DFS_distance(ll, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   84 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:84:9: note: in expansion of macro 'REP'
   84 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void WTree::Calc_farthest_down(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  113 |         REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i].ff);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:113:9: note: in expansion of macro 'REP'
  113 |         REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i].ff);}
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  114 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:114:9: note: in expansion of macro 'REP'
  114 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void WTree::Calc_farthest_up(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  126 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:126:9: note: in expansion of macro 'REP'
  126 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  131 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:131:9: note: in expansion of macro 'REP'
  131 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  137 |             REP(j,0,adj[c].size()) {if(adj[c][j].ff==s) {farthest_dir[c][j]=farthest_up[c];}}
      |                 ~~~~~~~~~~~~~~~~~
dreaming.cpp:137:13: note: in expansion of macro 'REP'
  137 |             REP(j,0,adj[c].size()) {if(adj[c][j].ff==s) {farthest_dir[c][j]=farthest_up[c];}}
      |             ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  139 |         REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i].ff);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:139:9: note: in expansion of macro 'REP'
  139 |         REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i].ff);}
      |         ^~~
dreaming.cpp: In member function 'void WG::DFS(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  186 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:186:9: note: in expansion of macro 'REP'
  186 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'std::vector<WTree> WG::CCG()':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  215 |         REP(cc,0,CC.size())
      |             ~~~~~~~~~~~~~~       
dreaming.cpp:215:9: note: in expansion of macro 'REP'
  215 |         REP(cc,0,CC.size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  226 |                 REP(j,0,adj[a].size()) {b=adj[a][j].ff; ad[i].pb({m[b],adj[a][j].ss});}
      |                     ~~~~~~~~~~~~~~~~~
dreaming.cpp:226:17: note: in expansion of macro 'REP'
  226 |                 REP(j,0,adj[a].size()) {b=adj[a][j].ff; ad[i].pb({m[b],adj[a][j].ss});}
      |                 ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<WTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  246 |  REP(i,0,F.size()) {F[i].Calc_Diametre(); ans=max(ans,F[i].diametre.ff);}
      |      ~~~~~~~~~~~~                
dreaming.cpp:246:2: note: in expansion of macro 'REP'
  246 |  REP(i,0,F.size()) {F[i].Calc_Diametre(); ans=max(ans,F[i].diametre.ff);}
      |  ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<WTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  247 |  vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
      |                    ~~~~~~~~~~~~  
dreaming.cpp:247:16: note: in expansion of macro 'REP'
  247 |  vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
      |                ^~~
dreaming.cpp:237:6: warning: unused variable 'a' [-Wunused-variable]
  237 |  int a;
      |      ^

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