oj.uz

답안 #402967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402967 2021-05-12T15:40:49 Z PedroBigMan 꿈 (IOI13_dreaming) C++14
14 / 100
 213 ms 65540 KB 
#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 Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
    vector<ll> val; //node values
    vector<vector<ll> > farthest_dir;
    vector<ll> farthest_down;
    vector<ll> farthest_up;
    vector<ll> farthest;
	vector<ll> dist;
	pair<ll,pl> diametre;
    
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        REP(i,0,N) {visited.pb(false);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);}
        DFS_Build(r,r);
        REP(i,0,N) {val.pb(0LL);}
        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]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
        return;
    }
	
	void DFS_distance(ll s, ll las)
    {
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i]==las) {continue;}
            dist[adj[s][i]]=dist[s]+val[adj[s][i]];
            DFS_distance(adj[s][i],s);
        }
    }
    
    void distance(ll s)
    {
        dist.clear(); REP(i,0,N) {dist.pb(INF);}
        dist[s]=val[s];
        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]);}
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i]==p[s]) {continue;}
            farthest_dir[s][i]=farthest_down[adj[s][i]]+val[adj[s][i]];
            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]==p[s]) {continue;}
            ll c = adj[s][i];
            if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+val[c];}
            else {farthest_up[c]=best_dis.ff+val[c];}
            REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
        }
        REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
    }
    
    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 WTree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<pl> > sons;
    vector<vector<pl> > adj;
    ll root;
    
    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);}
        DFS_Build(r,r);
    }
    
    void DFS_Build(ll s, ll par)
    {
        p[s]=par;
        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;
    }
    
    Tree Conv()
    {
        vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
        vector<ll> values; REP(i,0,N) {values.pb(0LL);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
        Tree T(ad,root); T.val=values; 
        return T;
    } 
};

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<Tree> CCG()
    {
        Reset();
        vector<Tree> 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.Conv());
        }
        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<Tree> 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()!=N-M) {while(1>0) {a++;}}
	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;
}

Compilation message

dreaming.cpp: In constructor 'Tree::Tree(std::vector<std::vector<int> >, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   63 |         REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
      |                         ~~~~~~~~~~~~~~~~~
dreaming.cpp:63:21: note: in expansion of macro 'REP'
   63 |         REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
      |                     ^~~
dreaming.cpp: In member function 'void Tree::DFS_Build(ll, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   75 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:75:9: note: in expansion of macro 'REP'
   75 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void Tree::DFS_distance(ll, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   86 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:86:9: note: in expansion of macro 'REP'
   86 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void Tree::Calc_farthest_down(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  115 |         REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i]);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:115:9: note: in expansion of macro 'REP'
  115 |         REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i]);}
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  116 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:116:9: note: in expansion of macro 'REP'
  116 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'void Tree::Calc_farthest_up(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  128 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:128:9: note: in expansion of macro 'REP'
  128 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  133 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:133:9: note: in expansion of macro 'REP'
  133 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  139 |             REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
      |                 ~~~~~~~~~~~~~~~~~
dreaming.cpp:139:13: note: in expansion of macro 'REP'
  139 |             REP(j,0,adj[c].size()) {if(adj[c][j]==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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  141 |         REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:141:9: note: in expansion of macro 'REP'
  141 |         REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
      |         ^~~
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++)
......
  182 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:182:9: note: in expansion of macro 'REP'
  182 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'Tree WTree::Conv()':
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++)
......
  195 |         REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
      |                         ~~~~~~~~~~~~~~~~~
dreaming.cpp:195:21: note: in expansion of macro 'REP'
  195 |         REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].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++)
......
  224 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:224:9: note: in expansion of macro 'REP'
  224 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In member function 'std::vector<Tree> 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++)
......
  253 |         REP(cc,0,CC.size())
      |             ~~~~~~~~~~~~~~       
dreaming.cpp:253:9: note: in expansion of macro 'REP'
  253 |         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++)
......
  264 |                 REP(j,0,adj[a].size()) {b=adj[a][j].ff; ad[i].pb({m[b],adj[a][j].ss});}
      |                     ~~~~~~~~~~~~~~~~~
dreaming.cpp:264:17: note: in expansion of macro 'REP'
  264 |                 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<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  284 |  REP(i,0,F.size()) {F[i].Calc_Diametre(); ans=max(ans,F[i].diametre.ff);}
      |      ~~~~~~~~~~~~                
dreaming.cpp:284:2: note: in expansion of macro 'REP'
  284 |  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<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  285 |  vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
      |                    ~~~~~~~~~~~~  
dreaming.cpp:285:16: note: in expansion of macro 'REP'
  285 |  vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
      |                ^~~
dreaming.cpp:287:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  287 |  if(R.size()!=N-M) {while(1>0) {a++;}}
      |     ~~~~~~~~^~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 61000 KB Output is correct
2 Correct 205 ms 60688 KB Output is correct
3 Correct 142 ms 40204 KB Output is correct
4 Correct 26 ms 9168 KB Output is correct
5 Correct 19 ms 5364 KB Output is correct
6 Correct 40 ms 13480 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 83 ms 22936 KB Output is correct
9 Correct 105 ms 29096 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 147 ms 38040 KB Output is correct
12 Correct 181 ms 48856 KB Output is correct
13 Correct 4 ms 844 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 61000 KB Output is correct
2 Correct 205 ms 60688 KB Output is correct
3 Correct 142 ms 40204 KB Output is correct
4 Correct 26 ms 9168 KB Output is correct
5 Correct 19 ms 5364 KB Output is correct
6 Correct 40 ms 13480 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 83 ms 22936 KB Output is correct
9 Correct 105 ms 29096 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 147 ms 38040 KB Output is correct
12 Correct 181 ms 48856 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 55536 KB Output is correct
2 Correct 210 ms 56004 KB Output is correct
3 Correct 205 ms 55364 KB Output is correct
4 Correct 205 ms 55992 KB Output is correct
5 Correct 207 ms 55312 KB Output is correct
6 Runtime error 172 ms 65540 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 61000 KB Output is correct
2 Correct 205 ms 60688 KB Output is correct
3 Correct 142 ms 40204 KB Output is correct
4 Correct 26 ms 9168 KB Output is correct
5 Correct 19 ms 5364 KB Output is correct
6 Correct 40 ms 13480 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 83 ms 22936 KB Output is correct
9 Correct 105 ms 29096 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 147 ms 38040 KB Output is correct
12 Correct 181 ms 48856 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -