oj.uz

Submission #244332

# Submission time Handle Problem Language Result Execution time Memory
244332 2020-07-03T16:08:18 Z AmineWeslati Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 1000 ms 6644 KB 
//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//s.order_of_key(), *s.find_by_order()

using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up

vi p;
vpi adj[50000];
bool vis[50000];
int sum;

void dfs(int u, int dest, int pr){
   if(u==dest) return;
   for(auto v: adj[u]) if(v.fi!=pr){
      p[v.fi]=u;
      dfs(v.fi,dest,u);
   }
}

int32_t main(){
   boost;
   int V; cin>>V;

   int s=0;
   for(int i=0; i<V-1; i++){

      int u,v,w; cin>>u>>v>>w;
      //u--; v--; //***************************************************************
      s+=w;
      adj[u].pb({v,w}),adj[v].pb({u,w});
   }

   int Q; cin>>Q;
	if(Q>100){
      vpi vec;
      int u;
      for(int i=0; i<V; i++) if(sz(adj[i])==1){u=i; break;}
      vec.pb({u,0});

      int p=-1;
      while(1){
         for(auto v: adj[u]) if(v.fi!=p){
            vec.pb(v);
            p=u;
            u=v.fi;
            break;
         }
         if(sz(adj[u])==1) break;
      }

      int t[V];
      for(int i=0; i<V; i++){
         t[vec[i].fi]=i;
         if(i) vec[i].se+=vec[i-1].se;
      }
      //for(int i=0; i<sz(vec); i++) cout << vec[i].fi << ' ' << vec[i].se << endl;

      while(Q--){
         int tab[5];
         for(int i=0; i<5;i++){cin>>tab[i]; tab[i]=t[tab[i]];}
         if(V==5){
            cout << s << endl; continue;
         }
         sort(tab,tab+5);
         int l=tab[0], r=tab[4];
         cout << vec[r].se-vec[l].se << endl;
      }
	}
	else{
      while(Q--){
         int t[5];
         p.assign(V,-1);
         for(int i=0; i<5; i++) cin>>t[i];
         memset(vis,false,sizeof(vis));
         sum=0;
         for(int i=0; i<5; i++) for(int j=i+1; j<5; j++){
            dfs(t[i],t[j],-1);

            int u=t[j];
            while(1){
               //cout << u << endl;
               if(u==t[i]){
                  vis[u]=true; break;
               }
               if(!(vis[u] && vis[p[u]])){
                  vis[u]=true;
                  for(auto x: adj[u]) if(x.fi==p[u]) sum+=x.se;
               }
               u=p[u];
            }
            //cout << sum << endl;
         }

         cout << sum << endl;

      }
	}

   return 0;
}

Compilation message

roadsideadverts.cpp: In function 'int32_t main()':
roadsideadverts.cpp:76:11: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
       int u;
           ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6124 KB Output is correct
2 Correct 40 ms 6644 KB Output is correct
3 Correct 39 ms 6508 KB Output is correct
4 Correct 43 ms 6640 KB Output is correct
5 Correct 38 ms 6636 KB Output is correct
6 Correct 42 ms 6636 KB Output is correct
7 Correct 40 ms 6644 KB Output is correct
8 Correct 40 ms 6636 KB Output is correct
9 Correct 39 ms 6516 KB Output is correct
10 Correct 43 ms 6636 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 5240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 35 ms 6124 KB Output is correct
3 Correct 40 ms 6644 KB Output is correct
4 Correct 39 ms 6508 KB Output is correct
5 Correct 43 ms 6640 KB Output is correct
6 Correct 38 ms 6636 KB Output is correct
7 Correct 42 ms 6636 KB Output is correct
8 Correct 40 ms 6644 KB Output is correct
9 Correct 40 ms 6636 KB Output is correct
10 Correct 39 ms 6516 KB Output is correct
11 Correct 43 ms 6636 KB Output is correct
12 Execution timed out 1091 ms 5240 KB Time limit exceeded
13 Halted 0 ms 0 KB -