oj.uz

답안 #127637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127637 2019-07-09T18:57:15 Z OptxPrime Valley (BOI19_valley) C++11
100 / 100
 620 ms 59044 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3192 KB Output is correct
3 Correct 32 ms 3192 KB Output is correct
4 Correct 32 ms 3192 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3192 KB Output is correct
3 Correct 32 ms 3192 KB Output is correct
4 Correct 32 ms 3192 KB Output is correct
5 Correct 8 ms 3320 KB Output is correct
6 Correct 8 ms 3320 KB Output is correct
7 Correct 8 ms 3320 KB Output is correct
8 Correct 8 ms 3320 KB Output is correct
9 Correct 8 ms 3320 KB Output is correct
10 Correct 8 ms 3320 KB Output is correct
11 Correct 8 ms 3320 KB Output is correct
12 Correct 8 ms 3324 KB Output is correct
13 Correct 9 ms 3320 KB Output is correct
14 Correct 20 ms 3320 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 56988 KB Output is correct
2 Correct 553 ms 56632 KB Output is correct
3 Correct 580 ms 56436 KB Output is correct
4 Correct 620 ms 58096 KB Output is correct
5 Correct 543 ms 57052 KB Output is correct
6 Correct 576 ms 58864 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3192 KB Output is correct
3 Correct 32 ms 3192 KB Output is correct
4 Correct 32 ms 3192 KB Output is correct
5 Correct 8 ms 3320 KB Output is correct
6 Correct 8 ms 3320 KB Output is correct
7 Correct 8 ms 3320 KB Output is correct
8 Correct 8 ms 3320 KB Output is correct
9 Correct 8 ms 3320 KB Output is correct
10 Correct 8 ms 3320 KB Output is correct
11 Correct 8 ms 3320 KB Output is correct
12 Correct 8 ms 3324 KB Output is correct
13 Correct 9 ms 3320 KB Output is correct
14 Correct 20 ms 3320 KB Output is correct
15 Correct 558 ms 56988 KB Output is correct
16 Correct 553 ms 56632 KB Output is correct
17 Correct 580 ms 56436 KB Output is correct
18 Correct 620 ms 58096 KB Output is correct
19 Correct 543 ms 57052 KB Output is correct
20 Correct 576 ms 58864 KB Output is correct
21 Correct 528 ms 55936 KB Output is correct
22 Correct 557 ms 55480 KB Output is correct
23 Correct 537 ms 55416 KB Output is correct
24 Correct 590 ms 57468 KB Output is correct
25 Correct 570 ms 59044 KB Output is correct
26 Correct 508 ms 56176 KB Output is correct
27 Correct 579 ms 55684 KB Output is correct
28 Correct 582 ms 55644 KB Output is correct
29 Correct 574 ms 56696 KB Output is correct
30 Correct 591 ms 57032 KB Output is correct
31 Correct 513 ms 54904 KB Output is correct
32 Correct 563 ms 52472 KB Output is correct
33 Correct 559 ms 52344 KB Output is correct
34 Correct 570 ms 54008 KB Output is correct
35 Correct 562 ms 55544 KB Output is correct
36 Correct 554 ms 54392 KB Output is correct