Submission #127637

#	Time	Username	Problem	Language	Result	Execution time	Memory
127637		OptxPrime	Valley (BOI19_valley)	C++11	100 / 100	620 ms	59044 KiB

valley

#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long

    bool color[100010];
    vector<int> upd[100010];
    bool ispec[100010];
    long long dist[100010];
    long long dp[100010];
    long long inf=100000000000000000;
    int par[100010][30];
    long long path[100010][30];
    int lvl[100010];
    int n,s,q,e;
    pair<int,int> edge[100010];

    /*struct query{
        int color,town,id;
        query(){}
        query(int color,int town,int id):color(color),town(town),id(id){}
    } qlist[100010];*/
    struct susjed{
        int node,w,id;
        susjed(){}
        susjed(int node, long long w,int id):node(node),w(w),id(id){}
    };
    vector<vector<susjed>> adjl;
    struct result{
        int escape;
        long long minw;
    }res[100010];
    struct in{
        int color,town;
        in(){}
        in(int color, int town):color(color),town(town){}
    }qlist[100010];

    void dfs( int x, int p, long long len, int depth )
    {
        dist[x] = len;
        lvl[x]=depth;
        for( int i=0;i<upd[x].size();i++ ){

                int id = upd[x][i];
                 int c = qlist[ id ].color;
     //       int c = upd[x][i]
      //      int id=upd[x][i].id;
            res[id].escape = color[c]; /// da li ce pobjec zavisi samo je li dosad naiso na taj color
        }
        for( int i=0;i<adjl[x].size();i++ ){
            if( adjl[x][i].node==p ) continue;
            int c = adjl[x][i].id;
            color[c]=true; /// ukljucimo edge
            dfs( adjl[x][i].node,x, len + adjl[x][i].w, depth+1 );
            color[c]=false;
        }
    }
    void dfs2( int x, int p )
    {
        par[x][0]=p; /// za lca
        if( ispec[x] ) dp[x]=dist[x];   /// udaljenost od roota
        else dp[x] = inf;
        for( int i=0;i<adjl[x].size();i++ ){
                if( adjl[x][i].node ==p ) continue;
            dfs2( adjl[x][i].node, x );
        dp[x]=min(dp[x], dp[ adjl[x][i].node ] ); /// minimum od djece
        }
    }

   /* long long lca( int a, int b )
    {
        long long res=inf;
        if( lvl[a] < lvl[b] ) swap(a,b);
        int logg;
        for( logg=0;(1<<logg)<=n;logg++ );
        logg--;
        for( int  i=logg;i>=0;i-- ){
            if( lvl[a] - ( 1<<i ) >= lvl[b] ) a=par[a][i];
        }
        if( a==b ) return a;
        for( int i=logg;i>=0;i-- ){
            if( par[a][i] !=-1 && par[a][i] != par[b][i] ){
                a=par[a][i];
                b=par[b][i];
            }
        }
        return par[a][0];
    }*/
    /// dzaba kuco lca kad mi ne treva??? samo mi treba bin lifting

    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int u,v;
        long long w;
        cin>>n>>s>>q>>e;
        e--;
        adjl.resize(n);

        for( int i=0;i<n-1;i++ ){
            cin>>u>>v>>w;
            u--;
            v--;
            edge[i] = mp( u,v );
            adjl[u].pb( susjed( v,w,i ) );
            adjl[v].pb( susjed( u,w,i ) );
        }
        int tmp;
        vector<int> spec;
        for( int i=0;i<s;i++ ){
            cin>>tmp;
            tmp--;
            spec.pb( tmp );
            ispec[tmp]=true;
        }
        int l,r;
         for( int i=0;i<q;i++ ){
            cin>>l>>r;
            l--;
            r--;
            qlist[i] = in(l,r);
            upd[r].pb( i );
         }
         for( int j=0;(1<<j)<=n;j++ ){
                for( int i=0;i<n;i++ ) par[i][j]= path[i][j]=-1;
            }       ///precalc lca

            dfs( e,e,0,0 );   /// dfs da offline izracuna samo moze li izaci
            dfs2( e,e );    /// drugi dfs, racuna lca dp
            for( int i=0;i<n;i++ ) {
                    if( dp[i]!=inf )
                    dp[i] -= 2*dist[i]; /// jer dp[i] nam cuva -2*dist[i] + min dist u subtree
            }
            /// cini se i ovaj dp dobar
          /*  for( int i = 0;i<n;i++ ){
                cout << i << " " <<  dp[i] << " kontas " <<endl;
            }
            for( int i =0;i<n;i++ ){
                cout << i << " " << dist[i] << " ee " <<endl;
            }*/
            /// jos ostaje lca da odradimo
            for(int i=0;i<n;i++) path[i][0]=dp[i];
            for( int j=1;(1<<j)<=n;j++ ){
                for( int i=0;i<n;i++ ){
                    if( par[i][j-1]!=-1 ){
                        par[i][j] = par[ par[i][j-1] ][j-1];
                        path[i][j] =min( path[i][j-1], path[ par[i][j-1] ][j-1] );
                    }
                }
            }
        /*    for( int i=0;i<n;i++ ){
                cout<<par[i][0] <<  " " << par[i][1] << " " << path[i][0] << " " <<path[i][1] << " blecak " << dp[i]<<endl;
            }*/
        //cout << lca( 2,0 ) << " lekceeaa  "<<endl;
            for( int i=0;i<q;i++ ){
                if( res[i].escape == false ){   /// ako nije naisao na edge pokvareni. ovo radi provjerio sam
                  //  cout << i <<endl;
                    cout << "escaped"<<endl;
                }
                else{
                    int p;
                    int u=qlist[i].town;
                    long long dd=dist[u];
                    pair<int,int> ee = edge[ qlist[i].color ]; /// qlist[i].color je index edga
                    if( lvl[ ee.first ] >= lvl[ ee.second ] ) p = ee.first;
                    else p=ee.second;       /// ovo je dublji vertex medju dva u kveriju, do njega trazimo minimum
                    long long res=inf;
                    int logg;
                    for( logg =0 ;(1<<logg)<=n;logg++ );
                    logg--;
                    for( int j=logg;j>=0;j-- ){
                        if( lvl[u] - (1<<j) >= lvl[p] ){
                             //   cout << i << " " << j << " oko  " <<endl;
                            res=min(res, path[u][j] );
                            u=par[u][j];
                        }
                    }
                    res=min( res, path[u][0]);
                    if( res!=inf )
                    cout<<res+dd<<endl;
                    else cout <<"oo"<<endl;
                   // cout << i << " " << p << " " << u << " bruda " <<endl;
                }
            }

      return 0;
    }

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, long long int, int)':
valley.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<upd[x].size();i++ ){
                      ~^~~~~~~~~~~~~~
valley.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<adjl[x].size();i++ ){
                      ~^~~~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<adjl[x].size();i++ ){
                      ~^~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41