Submission #380980

#	Time	Username	Problem	Language	Result	Execution time	Memory
380980		PedroBigMan	Firefighting (NOI20_firefighting)	C++14	36 / 100	3065 ms	1048580 KiB

Firefighting

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll ans; ll K; vector<ll> f_ans;

class SucPath
{
    public:
    ll N;
    vector<ll> fo;
    vector<vector<ll> > f2; //sparse table of steps powers of 2
    ll ms; //max_steps
    
    SucPath() {N=0LL;}
    SucPath(vector<ll> x, ll max_steps) 
    {
        N=x.size(); fo=x; ms=max_steps;
        vector<ll> xx;
        REP(i,0,(ll) (floor(log2(ms)))+1LL) {xx.pb(0LL);}
        REP(i,0,N) {f2.pb(xx);}
        Conf2(0);
    }
    
    void Conf2(ll e) //O(NlogN)
    {
        if((1LL<<e)>ms) {return;}
        if(e==0) {REP(i,0,N) {f2[i][e]=fo[i];} Conf2(e+1);}
        else 
        {
            REP(i,0,N) 
            {
                f2[i][e]=f2[f2[i][e-1]][e-1];
            }
        }
        Conf2(e+1);
    }
    
    ll f(ll x,ll s) //O(logN)
    {
        ll ind=0; 
        while(s>0) 
        {
            if(s%2!=0) {x=f2[x][ind];}
            s/=2; ind++;
        }
        return x;
    }
    
    pl cycle() //Floyd's Algorithm, O(N) time, O(1) memory, return <element of cycle,length od cycle>
    {
        ll a=fo[0]; ll b=fo[fo[0]];
        while(a!=b) {a=fo[a]; b=fo[fo[b]];}
        ll l=1; b=fo[a];
        while(b!=a) {b=fo[b]; l++;}
        return mp(a,l);
    }
};

class SparseTable //Range Minimum Queries
{
    public:
    ll N; 
    vector<pl> a;
    vector<vector<pl> > v;
    
    SparseTable() {N=0LL;}
    SparseTable(vector<pl> b)
    {
        a=b; N=a.size();
        ll lo=(ll) floor((double) log2(N)) +1LL;
        vector<pl> xx; 
        REP(i,0,lo) {xx.pb(mp(INF,INF));} REP(i,0,N) {v.pb(xx);}
        REP(step,0LL,lo)
        {
            REP(i,0,N-(1LL<<step)+1LL)
            {
                if(step==0) {v[i][0]=a[i];}
                else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
            }
        }
    }
    
    pl query(ll l, ll r)
    {
        ll step=(ll) floor((double) log2(r-l+1LL));
        return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
    }
};

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    vector<ll> level;
    vector<set<ll> > sonsset;
    ll root;
    vector<bool> visited;
    vector<ll> val; //node values
    
    Tree() {N=0LL;}
    Tree(vector<vector<ll> > ad, ll r)
    {
        N=ad.size(); root=r; adj=ad;
        set<ll> xxx; REP(i,0,N) {sonsset.pb(xxx);}
        REP(i,0,N) {visited.pb(false); level.pb(0LL);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);;}
        DFS_Build(r,r);
        REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
        p[s]=par;
        if(s!=root) {level[s]=level[par]+1LL;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
        return;
    }
    
    void DFS(ll s, ll curd, ll las)
    {
        if(curd<=K) {visited[s]=true;} else {return;}
        REP(i,0,sons[s].size()) 
        {
            if(sons[s][i]!=las) {DFS(sons[s][i], curd+val[sons[s][i]],s);}
        }
        if(p[s]!=las) {DFS(p[s],curd+val[s],s);}
    }
};

Tree H;

class WTree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<pl> > sons;
    vector<vector<pl> > adj;
    ll root;
    vector<ll> level; //starting in 0
    
    WTree(vector<vector<pl> > ad, ll r)
    {
        N=ad.size(); root=r; adj=ad;
        vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0);}
        DFS_Build(r,r);
    }
    
    void DFS_Build(ll s, ll par)
    {
        if(s!=root) {level[s]=level[par]+1LL;}
        p[s]=par;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i].ff==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i].ff,s);
        }
        return;
    }
    
    void DFS(ll s)
    {
        REP(i,0,sons[s].size()) 
        {
            DFS(sons[s][i].ff);
        }
    }
    
    Tree Conv()
    {
        vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
        vector<ll> values; REP(i,0,N) {values.pb(0LL);}
        REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
        Tree T(ad,root); T.val=values; 
        return T;
    }
};

void Sub(vector<bool> v, ll k)
{
    if(k==v.size()) 
    {
        ll N=v.size();
        ll susize=0LL; 
        REP(i,0,N)
        {
            if(!v[i]) {continue;}
            susize++;
            H.DFS(i,0LL,-1LL);
        }
        bool done=true; REP(i,0,N) {if(!H.visited[i]) {done=false;}}
        H.Reset(); 
        if(done) 
        {
            if(susize<ans) 
            {
                ans=susize;
                f_ans.clear();
                REP(i,0,N) {if(v[i]) {f_ans.pb(i+1);}}
            }
        }
    }
    else 
    {
        Sub(v,k+1LL);
        v[k]=true;
        Sub(v,k+1LL);
        v[k]=false;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N; cin>>N>>K; pl cur; ll we; vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
    REP(i,0,N-1)
    {
        cin>>cur.ff>>cur.ss>>we; cur.ff--; cur.ss--;
        adj[cur.ff].pb(mp(cur.ss,we)); adj[cur.ss].pb(mp(cur.ff,we));
    }
    WTree T(adj,0);
    H=T.Conv();
    bool task1=true; if(K>20LL) {task1=false;}
    REP(i,1,N) {if(H.val[i]<30LL) {task1=false;}}
    if(task1) {cout<<N<<endl; REP(i,0,N) {cout<<i+1<<" ";} cout<<endl; return 0;}
    bool task4=true;
    if(K>30LL) {task4=false;}
    REP(i,1,N) {if(H.val[i]<20LL) {task4=false;}}
    if(task4)
    {
        vector<ll> ans;
        unordered_map<ll,vector<ll> > m;
        ll ml=0LL;
        REP(i,0,N) {m[H.level[i]].pb(i); ml=max(ml,H.level[i]);}
        vector<bool> v; REP(i,0,N) {v.pb(true);}
        for(ll lev=ml;lev>0;lev--)
        {
            REP(i,0,m[lev].size())
            {
                ll node=m[lev][i];
                if(!v[node]) {continue;}
                if(H.val[node]>K) {ans.pb(node); v[node]=false;}
                else 
                {
                    ll par=H.p[node];
                    ans.pb(par); 
                    REP(j,0,H.sons[par].size()) 
                    {
                        if(H.val[H.sons[par][j]]<=K) {v[H.sons[par][j]]=false;}
                    }
                    v[par]=false;
                    if(H.val[par]<=K) {v[H.p[par]]=false;}
                }
            }
        }
        if(v[0]) {ans.pb(0);}
        cout<<ans.size()<<endl;
        REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
        cout<<endl;
        return 0;
    }
    ans=N+1; vector<bool> dummy; REP(i,0,N) {dummy.pb(false);}
    H.Reset();
    Sub(dummy,0LL);
    cout<<ans<<endl;
    Out(f_ans);
    return 0;
}

Compilation message (stderr)

Firefighting.cpp: In function 'void Out(std::vector<long long int>)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                             ~~~~~~~~~~~~
Firefighting.cpp:28:25: note: in expansion of macro 'REP'
   28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                         ^~~
Firefighting.cpp: In constructor 'Tree::Tree(std::vector<std::vector<long long int> >, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  136 |         REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
      |                         ~~~~~~~~~~~~~~~~~~
Firefighting.cpp:136:21: note: in expansion of macro 'REP'
  136 |         REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
      |                     ^~~
Firefighting.cpp: In member function 'void Tree::DFS_Build(ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  149 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
Firefighting.cpp:149:9: note: in expansion of macro 'REP'
  149 |         REP(i,0,adj[s].size())
      |         ^~~
Firefighting.cpp: In member function 'void Tree::DFS(ll, ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  161 |         REP(i,0,sons[s].size())
      |             ~~~~~~~~~~~~~~~~~~   
Firefighting.cpp:161:9: note: in expansion of macro 'REP'
  161 |         REP(i,0,sons[s].size())
      |         ^~~
Firefighting.cpp: In member function 'void WTree::DFS_Build(ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  192 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
Firefighting.cpp:192:9: note: in expansion of macro 'REP'
  192 |         REP(i,0,adj[s].size())
      |         ^~~
Firefighting.cpp: In member function 'void WTree::DFS(ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  203 |         REP(i,0,sons[s].size())
      |             ~~~~~~~~~~~~~~~~~~   
Firefighting.cpp:203:9: note: in expansion of macro 'REP'
  203 |         REP(i,0,sons[s].size())
      |         ^~~
Firefighting.cpp: In member function 'Tree WTree::Conv()':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  213 |         REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
      |                         ~~~~~~~~~~~~~~~~~
Firefighting.cpp:213:21: note: in expansion of macro 'REP'
  213 |         REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
      |                     ^~~
Firefighting.cpp: In function 'void Sub(std::vector<bool>, ll)':
Firefighting.cpp:221:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |     if(k==v.size())
      |        ~^~~~~~~~~~
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  279 |             REP(i,0,m[lev].size())
      |                 ~~~~~~~~~~~~~~~~~
Firefighting.cpp:279:13: note: in expansion of macro 'REP'
  279 |             REP(i,0,m[lev].size())
      |             ^~~
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  288 |                     REP(j,0,H.sons[par].size())
      |                         ~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:288:21: note: in expansion of macro 'REP'
  288 |                     REP(j,0,H.sons[par].size())
      |                     ^~~
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  299 |         REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
      |             ~~~~~~~~~~~~~~       
Firefighting.cpp:299:9: note: in expansion of macro 'REP'
  299 |         REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
      |         ^~~

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26
• Subtask 6: 0 / 38