fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool M1;
  5. //#define int long long
  6. #define ll long long
  7. #define pb push_back
  8. #define ii pair<int,int>
  9. #define len(s) (int)s.size()
  10. #define all(s) (s).begin(),(s).end()
  11. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  12. #define MASK(x) ((1LL)<<(x))
  13. #define Bit(x,i) (((x)>>(i))&1)
  14. #define Countbit(x) __builtin_popcountll(x)
  15.  
  16. template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
  17. template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
  18.  
  19. const int N=2e5+5,M=1e3+5,INF=1e9,lim=2e5;
  20. ll Mod=1e9+7,LNF=1e18;
  21.  
  22. int n,k,timer=0;
  23. int tin[N],tout[N],sz[N],heavy[N],node[N];
  24. ll f[N],dp[N],h[N];
  25. vector<ii> g[N];
  26. vector<ll> val;
  27.  
  28. int get_id(ll x) {
  29.     int pos=lower_bound(all(val),x)-val.begin();
  30.     if (pos<len(val) && val[pos]==x) return pos+1;
  31.     return -1;
  32. }
  33.  
  34. void DFS(int u=1,int p=0) {
  35.     tin[u]=++timer;
  36.     node[timer]=u;
  37.     sz[u]=1;
  38.     val.pb(f[u]);
  39.  
  40.     for (ii i:g[u])
  41.     if (i.first!=p) {
  42.         int v=i.first,w=i.second;
  43.         h[v]=h[u]+1;
  44.         f[v]=f[u]+w;
  45.         DFS(v,u);
  46.         sz[u]+=sz[v];
  47.         if (sz[v]>sz[heavy[u]]) heavy[u]=v;
  48.     }
  49.  
  50.     tout[u]=timer;
  51. }
  52.  
  53. ll res=LNF;
  54.  
  55. /// h[u]+h[v]-2*h[lca(u,v)]=k
  56. /// h[v]=k-h[u]+2*h[lca(u,v)]
  57.  
  58. void get(int u,int lca_uv) {
  59.     ll w=k-f[u]+2*f[lca_uv];
  60.     int id=get_id(w);
  61.  
  62.     if (id!=-1 && dp[id]!=LNF) Minimize(res,h[u]+dp[id]-2*h[lca_uv]);
  63. }
  64.  
  65. void Push(int u) {
  66.     int id=get_id(f[u]);
  67.     Minimize(dp[id],h[u]);
  68. }
  69.  
  70. void Pop(int u) {
  71.     int id=get_id(f[u]);
  72.     dp[id]=LNF;
  73. }
  74.  
  75. void sack(int u=1,int p=-1,bool keep=false) {
  76.     for (ii i:g[u]) {
  77.         int v=i.first;
  78.         if (v!=p && v!=heavy[u]) sack(v,u,0);
  79.     }
  80.     if (heavy[u]) sack(heavy[u],u,1);
  81.  
  82.     for (ii i:g[u]) {
  83.         int v=i.first;
  84.         if (v!=p && v!=heavy[u]) {
  85.             for (int j=tin[v];j<=tout[v];++j) get(node[j],u);
  86.             for (int j=tin[v];j<=tout[v];++j) Push(node[j]);
  87.         }
  88.     }
  89.  
  90.     get(u,u);
  91.     Push(u);
  92.  
  93.     if (keep==false)
  94.     for (int i=tin[u];i<=tout[u];++i) Pop(node[i]);
  95. }
  96.  
  97.  
  98. bool M2;
  99. signed main() {
  100.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  101.     OpenFile("TASK");
  102.  
  103.     cin>>n>>k;
  104.     for (int i=1;i<n;++i) {
  105.         int u,v,w; cin>>u>>v>>w;
  106.         u++;
  107.         v++;
  108.  
  109.         g[u].pb({v,w});
  110.         g[v].pb({u,w});
  111.     }
  112.  
  113.     DFS();
  114.     sort(all(val));
  115.     val.erase(unique(all(val)),val.end());
  116.  
  117.     for (int i=1;i<=lim;++i) dp[i]=LNF;
  118.  
  119.     sack();
  120.  
  121.     if (res==LNF) cout<<-1; else cout<<res;
  122.  
  123.  
  124.  
  125.     cerr<<"Time: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  126.     cerr<<"Memory: "<<abs(&M2-&M1)/1024.0/1024<<" MB\n";
  127.     return 0;
  128. }
  129.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:4: error: class, interface, or enum expected
bool M1;
^
Main.java:6: error: illegal character: '#'
#define ll long long
^
Main.java:6: error: class, interface, or enum expected
#define ll long long
        ^
Main.java:7: error: illegal character: '#'
#define pb push_back
^
Main.java:8: error: illegal character: '#'
#define ii pair<int,int>
^
Main.java:9: error: illegal character: '#'
#define len(s) (int)s.size()
^
Main.java:10: error: illegal character: '#'
#define all(s) (s).begin(),(s).end()
^
Main.java:11: error: illegal character: '#'
#define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
^
Main.java:12: error: illegal character: '#'
#define MASK(x) ((1LL)<<(x))
^
Main.java:12: error: class, interface, or enum expected
#define MASK(x) ((1LL)<<(x))
        ^
Main.java:13: error: illegal character: '#'
#define Bit(x,i) (((x)>>(i))&1)
^
Main.java:14: error: illegal character: '#'
#define Countbit(x) __builtin_popcountll(x)
^
Main.java:16: error: '{' expected
template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
                 ^
Main.java:16: error: illegal start of type
template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
                                             ^
Main.java:16: error: <identifier> expected
template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
                                                  ^
Main.java:16: error: <identifier> expected
template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
                                                    ^
Main.java:16: error: illegal start of type
template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
                                                                            ^
Main.java:17: error: class, interface, or enum expected
template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
^
Main.java:17: error: '{' expected
template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
                 ^
Main.java:17: error: illegal start of type
template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
                                             ^
Main.java:17: error: > expected
template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
                                                    ^
Main.java:17: error: illegal start of type
template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
                                                                            ^
Main.java:19: error: class, interface, or enum expected
const int N=2e5+5,M=1e3+5,INF=1e9,lim=2e5;
^
Main.java:20: error: class, interface, or enum expected
ll Mod=1e9+7,LNF=1e18;
^
Main.java:22: error: class, interface, or enum expected
int n,k,timer=0;
^
Main.java:23: error: class, interface, or enum expected
int tin[N],tout[N],sz[N],heavy[N],node[N];
^
Main.java:24: error: class, interface, or enum expected
ll f[N],dp[N],h[N];
^
Main.java:25: error: class, interface, or enum expected
vector<ii> g[N];
^
Main.java:26: error: class, interface, or enum expected
vector<ll> val;
^
Main.java:28: error: class, interface, or enum expected
int get_id(ll x) {
^
Main.java:30: error: class, interface, or enum expected
    if (pos<len(val) && val[pos]==x) return pos+1;
    ^
Main.java:31: error: class, interface, or enum expected
    return -1;
    ^
Main.java:32: error: class, interface, or enum expected
}
^
Main.java:36: error: class, interface, or enum expected
    node[timer]=u;
    ^
Main.java:37: error: class, interface, or enum expected
    sz[u]=1;
    ^
Main.java:38: error: class, interface, or enum expected
    val.pb(f[u]);
    ^
Main.java:40: error: class, interface, or enum expected
    for (ii i:g[u])
    ^
Main.java:43: error: class, interface, or enum expected
        h[v]=h[u]+1;
        ^
Main.java:44: error: class, interface, or enum expected
        f[v]=f[u]+w;
        ^
Main.java:45: error: class, interface, or enum expected
        DFS(v,u);
        ^
Main.java:46: error: class, interface, or enum expected
        sz[u]+=sz[v];
        ^
Main.java:47: error: class, interface, or enum expected
        if (sz[v]>sz[heavy[u]]) heavy[u]=v;
        ^
Main.java:48: error: class, interface, or enum expected
    }
    ^
Main.java:51: error: class, interface, or enum expected
}
^
Main.java:58: error: class, interface, or enum expected
void get(int u,int lca_uv) {
^
Main.java:60: error: class, interface, or enum expected
    int id=get_id(w);
    ^
Main.java:62: error: class, interface, or enum expected
    if (id!=-1 && dp[id]!=LNF) Minimize(res,h[u]+dp[id]-2*h[lca_uv]);
    ^
Main.java:63: error: class, interface, or enum expected
}
^
Main.java:67: error: class, interface, or enum expected
    Minimize(dp[id],h[u]);
    ^
Main.java:68: error: class, interface, or enum expected
}
^
Main.java:72: error: class, interface, or enum expected
    dp[id]=LNF;
    ^
Main.java:73: error: class, interface, or enum expected
}
^
Main.java:78: error: class, interface, or enum expected
        if (v!=p && v!=heavy[u]) sack(v,u,0);
        ^
Main.java:79: error: class, interface, or enum expected
    }
    ^
Main.java:82: error: class, interface, or enum expected
    for (ii i:g[u]) {
    ^
Main.java:84: error: class, interface, or enum expected
        if (v!=p && v!=heavy[u]) {
        ^
Main.java:85: error: class, interface, or enum expected
            for (int j=tin[v];j<=tout[v];++j) get(node[j],u);
                              ^
Main.java:85: error: class, interface, or enum expected
            for (int j=tin[v];j<=tout[v];++j) get(node[j],u);
                                         ^
Main.java:86: error: class, interface, or enum expected
            for (int j=tin[v];j<=tout[v];++j) Push(node[j]);
            ^
Main.java:86: error: class, interface, or enum expected
            for (int j=tin[v];j<=tout[v];++j) Push(node[j]);
                              ^
Main.java:86: error: class, interface, or enum expected
            for (int j=tin[v];j<=tout[v];++j) Push(node[j]);
                                         ^
Main.java:87: error: class, interface, or enum expected
        }
        ^
Main.java:91: error: class, interface, or enum expected
    Push(u);
    ^
Main.java:93: error: class, interface, or enum expected
    if (keep==false)
    ^
Main.java:94: error: class, interface, or enum expected
    for (int i=tin[u];i<=tout[u];++i) Pop(node[i]);
                      ^
Main.java:94: error: class, interface, or enum expected
    for (int i=tin[u];i<=tout[u];++i) Pop(node[i]);
                                 ^
Main.java:95: error: class, interface, or enum expected
}
^
Main.java:99: error: class, interface, or enum expected
signed main() {
^
Main.java:100: error: class, interface, or enum expected
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
                                      ^
Main.java:100: error: class, interface, or enum expected
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
                                                  ^
Main.java:101: error: class, interface, or enum expected
    OpenFile("TASK");
    ^
Main.java:103: error: class, interface, or enum expected
    cin>>n>>k;
    ^
Main.java:104: error: class, interface, or enum expected
    for (int i=1;i<n;++i) {
    ^
Main.java:104: error: class, interface, or enum expected
    for (int i=1;i<n;++i) {
                 ^
Main.java:104: error: class, interface, or enum expected
    for (int i=1;i<n;++i) {
                     ^
Main.java:105: error: class, interface, or enum expected
        int u,v,w; cin>>u>>v>>w;
                   ^
Main.java:106: error: class, interface, or enum expected
        u++;
        ^
Main.java:107: error: class, interface, or enum expected
        v++;
        ^
Main.java:109: error: class, interface, or enum expected
        g[u].pb({v,w});
        ^
Main.java:110: error: class, interface, or enum expected
        g[v].pb({u,w});
        ^
Main.java:111: error: class, interface, or enum expected
    }
    ^
Main.java:114: error: class, interface, or enum expected
    sort(all(val));
    ^
Main.java:115: error: class, interface, or enum expected
    val.erase(unique(all(val)),val.end());
    ^
Main.java:117: error: class, interface, or enum expected
    for (int i=1;i<=lim;++i) dp[i]=LNF;
    ^
Main.java:117: error: class, interface, or enum expected
    for (int i=1;i<=lim;++i) dp[i]=LNF;
                 ^
Main.java:117: error: class, interface, or enum expected
    for (int i=1;i<=lim;++i) dp[i]=LNF;
                        ^
Main.java:119: error: class, interface, or enum expected
    sack();
    ^
Main.java:121: error: class, interface, or enum expected
    if (res==LNF) cout<<-1; else cout<<res;
    ^
Main.java:121: error: class, interface, or enum expected
    if (res==LNF) cout<<-1; else cout<<res;
                            ^
Main.java:125: error: class, interface, or enum expected
    cerr<<"Time: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
    ^
Main.java:126: error: class, interface, or enum expected
    cerr<<"Memory: "<<abs(&M2-&M1)/1024.0/1024<<" MB\n";
    ^
Main.java:127: error: class, interface, or enum expected
    return 0;
    ^
Main.java:128: error: class, interface, or enum expected
}
^
95 errors
stdout
copy 
Standard output is empty
https://ideone.com/yaOPcn
language:
Java (HotSpot 12)
created:
5 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!