Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define forsn(i, s, n) for(int i=s;i<int(n);i++)
- #define forn(i, n) forsn(i, 0, n)
- #define all(v) v.begin(), v.end()
- #define NACHO ios_base::sync_with_stdio(0);cin.tie(NULL);
- vector<bool> visited;
- typedef long long tint;
- void dfs(int node, vector<vector<pair<int,int>>> &adj, vector<int> &dist){
- visited[node] = 1;
- for(auto u : adj[node]){
- if(!visited[u.first]){
- dist[u.first] = dist[node]+u.second;
- dfs(u.first, adj, dist);
- }
- }
- }
- tint sz[300001];
- void fill(int node, vector<vector<pair<int,int>>> &adj){
- visited[node] = 1;
- for(auto u : adj[node]){
- if(!visited[u.first]){
- sz[node]+=u.second;
- fill(u.first, adj);
- sz[node]+=sz[u.first];
- }
- }
- }
- vector<int> chemin;
- void path(int node, vector<vector<pair<int,int>>> &adj){
- chemin.push_back(node);
- visited[node] = 1;
- int maxi = 0, nodo = -1;
- for(auto u : adj[node]){
- if(!visited[u.first]){
- if(sz[u.first] > maxi){maxi = sz[u.first]; nodo = u.first;}
- }
- }
- if(nodo == -1) return;
- path(nodo, adj);
- }
- int main(){
- ifstream cin("puesto.in");
- ofstream cout("puesto.out");
- int m; cin >> m;
- vector<vector<pair<int,int>>> adj (300001);
- vector<pair<int,int>> edges (m);
- forn(i, m){
- int u, v, w; cin >> u >> v >> w;
- u--; v--;
- adj[u].push_back({v, w});
- adj[v].push_back({u, w});
- edges[i] = {u, v};
- }
- visited.resize(300001, 0);
- vector<int> dist (300001, 0);
- dfs(0, adj, dist);
- int nodito;
- int maxi = 0;
- forn(i, 300001){
- if(dist[i] > maxi){
- maxi = dist[i];
- nodito = i;
- }
- }
- visited.clear();
- visited.resize(300001, 0);
- dist.clear();
- dist.resize(300001, 0);
- dfs(nodito, adj, dist);
- maxi = 0;
- forn(i, 300001){
- maxi = max(maxi, dist[i]);
- }
- visited.clear(); visited.resize(300001, 0);
- fill(0, adj);
- visited.clear(); visited.resize(300001, 0);
- path(nodito, adj);
- int best, bestt;
- for(int i=0;i<int(chemin.size());i++){
- if(dist[chemin[i]] > double(maxi/2.0)){
- best = chemin[i];
- bestt = chemin[i-1];
- break;
- }
- }
- visited.clear();
- visited.resize(300001, 0);
- dist.clear();
- dist.resize(300001, 0);
- dfs(bestt, adj, dist);
- bool one = 0;
- if(dist[nodito] == maxi/2.0){
- one = 1;
- }
- string s;
- //cout << dist[bestt] << endl;
- if(one){
- forn(i, m){
- if(dist[edges[i].first] < dist[edges[i].second]) s+='-';
- else s+='+';
- }
- }else{
- forn(i, m){
- if((edges[i].first == best && edges[i].second == bestt) || (edges[i].first == bestt && edges[i].second == best)) s+='0';
- else if(dist[edges[i].first] < dist[edges[i].second]) s+='-';
- else s+='+';
- }
- }
- cout << fixed << setprecision(1) << maxi/2.0 << "\n";
- cout << s << "\n";
- }
- //6
- //1 2 1
- //2 3 1
- //5 4 1
- //4 3 1
- //6 7 1
- //6 3 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement