Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forsn(i, s, n) for(int i=s;i<int(n);i++)
  6. #define forn(i, n) forsn(i, 0, n)
  7. #define all(v) v.begin(), v.end()
  8. #define NACHO ios_base::sync_with_stdio(0);cin.tie(NULL);
  9.  
  10. vector<bool> visited;
  11.  
  12. typedef long long tint;
  13.  
  14. void dfs(int node, vector<vector<pair<int,int>>> &adj, vector<int> &dist){
  15.     visited[node] = 1;
  16.     for(auto u : adj[node]){
  17.         if(!visited[u.first]){
  18.             dist[u.first] = dist[node]+u.second;
  19.             dfs(u.first, adj, dist);
  20.         }
  21.     }
  22. }
  23.  
  24. tint sz[300001];
  25.  
  26. void fill(int node, vector<vector<pair<int,int>>> &adj){
  27.     visited[node] = 1;
  28.     for(auto u : adj[node]){
  29.         if(!visited[u.first]){
  30.             sz[node]+=u.second;
  31.             fill(u.first, adj);
  32.             sz[node]+=sz[u.first];
  33.         }
  34.     }
  35. }
  36.  
  37. vector<int> chemin;
  38.  
  39. void path(int node, vector<vector<pair<int,int>>> &adj){
  40.     chemin.push_back(node);
  41.     visited[node] = 1;
  42.     int maxi = 0, nodo = -1;
  43.     for(auto u : adj[node]){
  44.         if(!visited[u.first]){
  45.             if(sz[u.first] > maxi){maxi = sz[u.first]; nodo = u.first;}
  46.         }
  47.     }
  48.     if(nodo == -1) return;
  49.     path(nodo, adj);
  50. }
  51.  
  52. int main(){
  53.     ifstream cin("puesto.in");
  54.     ofstream cout("puesto.out");
  55.     int m; cin >> m;
  56.     vector<vector<pair<int,int>>> adj (300001);
  57.     vector<pair<int,int>> edges (m);
  58.     forn(i, m){
  59.         int u, v, w; cin >> u >> v >> w;
  60.         u--; v--;
  61.         adj[u].push_back({v, w});
  62.         adj[v].push_back({u, w});
  63.         edges[i] = {u, v};
  64.     }
  65.     visited.resize(300001, 0);
  66.     vector<int> dist (300001, 0);
  67.     dfs(0, adj, dist);
  68.     int nodito;
  69.     int maxi = 0;
  70.     forn(i, 300001){
  71.         if(dist[i] > maxi){
  72.             maxi = dist[i];
  73.             nodito = i;
  74.         }
  75.     }
  76.     visited.clear();
  77.     visited.resize(300001, 0);
  78.     dist.clear();
  79.     dist.resize(300001, 0);
  80.     dfs(nodito, adj, dist);
  81.     maxi = 0;
  82.     forn(i, 300001){
  83.          maxi = max(maxi, dist[i]);
  84.     }
  85.     visited.clear(); visited.resize(300001, 0);
  86.     fill(0, adj);
  87.     visited.clear(); visited.resize(300001, 0);
  88.     path(nodito, adj);
  89.     int best, bestt;
  90.     for(int i=0;i<int(chemin.size());i++){
  91.         if(dist[chemin[i]] > double(maxi/2.0)){
  92.             best = chemin[i];
  93.             bestt = chemin[i-1];
  94.             break;
  95.         }
  96.     }
  97.     visited.clear();
  98.     visited.resize(300001, 0);
  99.     dist.clear();
  100.     dist.resize(300001, 0);
  101.     dfs(bestt, adj, dist);
  102.     bool one = 0;
  103.     if(dist[nodito] == maxi/2.0){
  104.         one = 1;
  105.     }
  106.     string s;
  107.     //cout << dist[bestt] << endl;
  108.     if(one){
  109.         forn(i, m){
  110.             if(dist[edges[i].first] < dist[edges[i].second]) s+='-';
  111.             else s+='+';
  112.         }
  113.     }else{
  114.         forn(i, m){
  115.             if((edges[i].first == best && edges[i].second == bestt) || (edges[i].first == bestt && edges[i].second == best)) s+='0';
  116.             else if(dist[edges[i].first] < dist[edges[i].second]) s+='-';
  117.             else s+='+';
  118.         }
  119.     }
  120.     cout << fixed << setprecision(1) << maxi/2.0 << "\n";
  121.     cout << s << "\n";
  122. }
  123. //6
  124. //1 2 1
  125. //2 3 1
  126. //5 4 1
  127. //4 3 1
  128. //6 7 1
  129. //6 3 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement