oj.uz

Submission #284425

# Submission time Handle Problem Language Result Execution time Memory
284425 2020-08-27T11:31:43 Z PedroBigMan Dreaming (IOI13_dreaming) C++14
0 / 100
 240 ms 60040 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 long long 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 50000000000LL

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);}} 

struct hash_pair 
{ 
    template <class T1, class T2> 
    size_t operator() (pair<T1, T2> p) const
    {
        size_t hash1 = hash<T1>()(p.first); 
        size_t hash2 = hash<T2>()(p.second); 
        return (hash1 ^ hash2); 
    } 
};

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<ll> visited; //for DFS/BFS
    vector<ll> current; //for CC
    
    Graph() {ll N=0LL;}
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
    }
    
    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]]) {DFS(adj[s][i]);}
        }
        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;
    }
};

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
    vector<ll> level; //starting in 0
    vector<ll> sub; //number of nodes in subtree
    vector<ll> val; //node values
    vector<ll> dist; 
    pair<ll,pl> diametre;
    vector<vector<ll> > farthest_dir;
    vector<ll> farthest_down;
    vector<ll> farthest_up;
    vector<ll> farthest;
    
    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); level.pb(0); sub.pb(1LL);}
        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)
    {
        if(s!=root) {level[s]=level[par]+1LL;}
        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);
            sub[s]+=sub[adj[s][i]];
        }
        return;
    }
    
    void DFS_distance(ll s, ll las)
    {
        REP(i,0,adj[s].size()) 
        {
            if(adj[s][i]==las) {continue;}
            if(adj[s][i]==p[s]) {dist[adj[s][i]]=dist[s]+val[s];}
            else {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]=0;
        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()
    {
        REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
    }
};

class WTree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<pl> > sons;
    vector<vector<pl> > adj;
    ll root;
    vector<ll> level; //starting in 0
    
    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); level.pb(0);}
        DFS_Build(r,r);
    }
    
    void DFS_Build(ll s, ll par)
    {
        if(s!=root) {level[s]=level[par]+1LL;}
        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);}
        Tree T(ad,root); return T;
        /*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;*/
    } 
};

int travelTime(int n, int M, int L, int A[], int B[], int T[]) 
{
    ll N = (ll) n;
    vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
    pl cur;
    REP(i,0,M)
    {
        cur=mp(A[i],B[i]); 
        adj[cur.ff].pb(cur.ss); adj[cur.ss].pb(cur.ff);
    }
    unordered_map<pl,ll,hash_pair> w;
    REP(i,0,M)
    {
        w[mp(A[i],B[i])]=T[i];
        w[mp(B[i],A[i])]=T[i];
    }
    Graph G(adj);
    vector<vector<ll> > H = G.CC();
    vector<Tree> F;
    REP(i,0,H.size())
    {
        vector<vector<pl> > ad; vector<pl> xxx; REP(j,0,H[i].size()) {ad.pb(xxx);}
        unordered_map<ll,ll> t; REP(j,0,H[i].size()) {t[H[i][j]]=j;}
        REP(j,0,H[i].size())
        {
            ll c = H[i][j];
            REP(z,0,adj[c].size()) {ad[t[c]].pb(mp(t[adj[c][z]],w[mp(c,adj[c][z])]));}
        }
        WTree T(ad);
        return 0;
        Tree T2 = T.Conv();
        return 0;
        F.pb(T2);
    }
    vector<ll> d; vector<ll> inner; 
    REP(i,0,F.size()) {F[i].Calc_Diametre(); d.pb(F[i].diametre.ff);}
    sort(whole(d)); reverse(whole(d));
    REP(i,0,F.size()) {F[i].Calc_farthest_down(F[i].root);}
    REP(i,0,F.size()) {F[i].Calc_farthest_up(F[i].root);}
    REP(i,0,F.size()) {F[i].Calc_farthest(); inner.pb(*min_element(whole(F[i].farthest)));}
    sort(whole(inner)); reverse(whole(inner));
    ll ans = d[0]; 
    if(F.size()>=2) {ans=max(ans,inner[0]+inner[1]+L);}
    if(F.size()>=3) {ans=max(ans,inner[1]+inner[2]+2LL*L);}
    return ans;
}

Compilation message

dreaming.cpp: In constructor 'Graph::Graph()':
dreaming.cpp:56:17: warning: unused variable 'N' [-Wunused-variable]
   56 |     Graph() {ll N=0LL;}
      |                 ^
dreaming.cpp: In member function 'void Graph::DFS(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   74 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:74:9: note: in expansion of macro 'REP'
   74 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp: In constructor 'Tree::Tree(std::vector<std::vector<long long int> >, ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long 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,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
      |                         ~~~~~~~~~~~~~~~~~
dreaming.cpp:126:21: note: in expansion of macro 'REP'
  126 |         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 'long long int'} and 'std::vector<long long 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,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:139:9: note: in expansion of macro 'REP'
  139 |         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 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  151 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:151:9: note: in expansion of macro 'REP'
  151 |         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 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  181 |         REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i]);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:181:9: note: in expansion of macro 'REP'
  181 |         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 'long long int'} and 'std::vector<long long 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 'void Tree::Calc_farthest_up(ll)':
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  194 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:194:9: note: in expansion of macro 'REP'
  194 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  199 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:199:9: note: in expansion of macro 'REP'
  199 |         REP(i,0,adj[s].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  205 |             REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
      |                 ~~~~~~~~~~~~~~~~~
dreaming.cpp:205:13: note: in expansion of macro 'REP'
  205 |             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 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  207 |         REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
      |             ~~~~~~~~~~~~~~~~~~   
dreaming.cpp:207:9: note: in expansion of macro 'REP'
  207 |         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 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  237 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
dreaming.cpp:237:9: note: in expansion of macro 'REP'
  237 |         REP(i,0,adj[s].size())
      |         ^~~
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 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  276 |     REP(i,0,H.size())
      |         ~~~~~~~~~~~~             
dreaming.cpp:276:5: note: in expansion of macro 'REP'
  276 |     REP(i,0,H.size())
      |     ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  278 |         vector<vector<pl> > ad; vector<pl> xxx; REP(j,0,H[i].size()) {ad.pb(xxx);}
      |                                                     ~~~~~~~~~~~~~~~
dreaming.cpp:278:49: note: in expansion of macro 'REP'
  278 |         vector<vector<pl> > ad; vector<pl> xxx; REP(j,0,H[i].size()) {ad.pb(xxx);}
      |                                                 ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  279 |         unordered_map<ll,ll> t; REP(j,0,H[i].size()) {t[H[i][j]]=j;}
      |                                     ~~~~~~~~~~~~~~~
dreaming.cpp:279:33: note: in expansion of macro 'REP'
  279 |         unordered_map<ll,ll> t; REP(j,0,H[i].size()) {t[H[i][j]]=j;}
      |                                 ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  280 |         REP(j,0,H[i].size())
      |             ~~~~~~~~~~~~~~~      
dreaming.cpp:280:9: note: in expansion of macro 'REP'
  280 |         REP(j,0,H[i].size())
      |         ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  283 |             REP(z,0,adj[c].size()) {ad[t[c]].pb(mp(t[adj[c][z]],w[mp(c,adj[c][z])]));}
      |                 ~~~~~~~~~~~~~~~~~
dreaming.cpp:283:13: note: in expansion of macro 'REP'
  283 |             REP(z,0,adj[c].size()) {ad[t[c]].pb(mp(t[adj[c][z]],w[mp(c,adj[c][z])]));}
      |             ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long 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++)
......
  292 |     REP(i,0,F.size()) {F[i].Calc_Diametre(); d.pb(F[i].diametre.ff);}
      |         ~~~~~~~~~~~~             
dreaming.cpp:292:5: note: in expansion of macro 'REP'
  292 |     REP(i,0,F.size()) {F[i].Calc_Diametre(); d.pb(F[i].diametre.ff);}
      |     ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long 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++)
......
  294 |     REP(i,0,F.size()) {F[i].Calc_farthest_down(F[i].root);}
      |         ~~~~~~~~~~~~             
dreaming.cpp:294:5: note: in expansion of macro 'REP'
  294 |     REP(i,0,F.size()) {F[i].Calc_farthest_down(F[i].root);}
      |     ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long 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++)
......
  295 |     REP(i,0,F.size()) {F[i].Calc_farthest_up(F[i].root);}
      |         ~~~~~~~~~~~~             
dreaming.cpp:295:5: note: in expansion of macro 'REP'
  295 |     REP(i,0,F.size()) {F[i].Calc_farthest_up(F[i].root);}
      |     ^~~
dreaming.cpp:21:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long 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++)
......
  296 |     REP(i,0,F.size()) {F[i].Calc_farthest(); inner.pb(*min_element(whole(F[i].farthest)));}
      |         ~~~~~~~~~~~~             
dreaming.cpp:296:5: note: in expansion of macro 'REP'
  296 |     REP(i,0,F.size()) {F[i].Calc_farthest(); inner.pb(*min_element(whole(F[i].farthest)));}
      |     ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 60040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 60040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 60040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 18788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 60040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 60040 KB Output isn't correct
2 Halted 0 ms 0 KB -