Submission #825840

# Submission time Handle Problem Language Result Execution time Memory
825840 2023-08-15T08:45:50 Z karrigan Parkovi (COCI22_parkovi) C++17
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+2;
const ll offset=1e9;
const ll block=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,k,g,up[maxn],select;
bool ed[maxn];
vector<pii> adj[maxn];
vector<int> res;
void cc(int u,int pass)
{
//    cerr<<"asdasd "<< u<<'\n';
    res.pb(u);
    up[u]=pass;
    ed[u]=1;
    select++;
}
void dfs(int u,int pre,int last)
{
    //cerr<<u<<'\n';
    for(auto x: adj[u])
    {
        int v=x.fi,w=x.se;
        if (v==pre) continue;
        dfs(v,u,w);
    }
    if (last>g)
    {
        cc(u,last);
        return;
    }
    int mx1=0,mx2=0;
    for(auto x: adj[u])
    {
        int v=x.fi,w=x.se;
        if (v==pre) continue;
        if (last+up[v]>g && !ed[v])
        {
            cc(u,last);
            return;
        }
        if (!ed[v])
        {
            if (up[v]>= mx1)
            {
                mx2=mx1;
                mx1=up[v];
            }
            else if (up[v]>=mx2)
            {
                mx2=up[v];
            }
        }

    }
//    if (u==3)
//    {
//        cerr<< mx1<<' '<< mx2<<'\n';
//    }
    if (mx1+mx2>g)
    {
        cc(u,last);
        return;
    }
    up[u]=mx1+last;
}
bool check(int l)
{
    res.clear();
    g=l;
    select=0;
    for1(i,1,n)
    {
        up[i]=0;
        ed[i]=0;
    }
    dfs(1,0,0);
//    cerr<< select<<'\n';
    return (select<=k);

}
void sol()
{
    cin >> n>> k;
    for1(i,1,n-1)
    {
        int u,v,w;cin >> u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    int l=0,r=1e14,mid;
    while (l<=r)
    {
        //cerr<< l<<'\n';
        mid=l+r>>1;
        if (check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout << l;
    cout << '\n';
    check(l);
    if (res.size()<k)
    {
        for1(i,1,n)
        {
            if (!ed[i]) res.pb(i);
            if (res.size()==k) break;
        }
    }
    for(int v: res) cout << v<<' ';
       // cerr<< check(8);

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;//cin >> t;
    while(t--)
    {
        sol();
    }
}
/*

6 3
2 1 7
3 1 2
3 4 6
1 5 9
1 6 6
*/


Compilation message

Main.cpp:25:20: error: 'long long int select' redeclared as different kind of entity
   25 | int n,k,g,up[maxn],select;
      |                    ^~~~~~
In file included from /usr/include/x86_64-linux-gnu/sys/types.h:179,
                 from /usr/include/stdlib.h:394,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:2:
/usr/include/x86_64-linux-gnu/sys/select.h:101:12: note: previous declaration 'int select(int, fd_set*, fd_set*, fd_set*, timeval*)'
  101 | extern int select (int __nfds, fd_set *__restrict __readfds,
      |            ^~~~~~
Main.cpp: In function 'void cc(long long int, long long int)':
Main.cpp:35:5: warning: ISO C++ forbids incrementing a pointer of type 'int (*)(int, fd_set*, fd_set*, fd_set*, timeval*)' [-Wpointer-arith]
   35 |     select++;
      |     ^~~~~~
Main.cpp:35:5: error: lvalue required as increment operand
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:54:20: warning: unused variable 'w' [-Wunused-variable]
   54 |         int v=x.fi,w=x.se;
      |                    ^
Main.cpp: In function 'bool check(long long int)':
Main.cpp:90:11: error: assignment of function 'int select(int, fd_set*, fd_set*, fd_set*, timeval*)'
   90 |     select=0;
      |     ~~~~~~^~
Main.cpp:98:19: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
   98 |     return (select<=k);
      |             ~~~~~~^~~
Main.cpp: In function 'void sol()':
Main.cpp:114:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         mid=l+r>>1;
      |             ~^~
Main.cpp:121:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  121 |     if (res.size()<k)
      |         ~~~~~~~~~~^~
Main.cpp:126:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  126 |             if (res.size()==k) break;
      |                 ~~~~~~~~~~^~~