Submission #226349

#	Time	Username	Problem	Language	Result	Execution time	Memory
226349		MKopchev	Tug of War (BOI15_tug)	C++14	100 / 100	1543 ms	11256 KiB

tug

#include<bits/stdc++.h>
using namespace std;
const int nmax=6e4+42;

int n,k;

struct edge
{
    int l,r,add;
};

edge inp[nmax];

set<int> adj[nmax];

void stop(bool ok)
{
    if(ok)printf("YES\n");
    else printf("NO\n");
    exit(0);
}

bool solved[nmax];

queue< pair<int/*size*/,int/*id*/> > to_place;

void cut_edge(int edge)
{
    //cout<<"cut_edge "<<edge<<endl;

    adj[inp[edge].l].erase(edge);
    adj[inp[edge].r].erase(edge);

    if(adj[inp[edge].l].size()<=1)to_place.push({adj[inp[edge].l].size(),inp[edge].l});
    if(adj[inp[edge].r].size()<=1)to_place.push({adj[inp[edge].r].size(),inp[edge].r});
}

bitset<10*nmax> can;

int main()
{
    scanf("%i%i",&n,&k);

    int total=0;

    int LHS=0,RHS=0;

    for(int i=1;i<=2*n;i++)
    {
        scanf("%i%i%i",&inp[i].l,&inp[i].r,&inp[i].add);
        inp[i].r+=n;

        adj[inp[i].l].insert(i);
        adj[inp[i].r].insert(i);

        total+=inp[i].add;
    }

    for(int i=1;i<=2*n;i++)
        if(adj[i].size()<=1)to_place.push({adj[i].size(),i});

    while(to_place.size())
    {
        pair<int/*size*/,int/*id*/> tp=to_place.front();
        to_place.pop();

        //cout<<"test "<<tp.second<<endl;

        if(solved[tp.second])continue;

        if(adj[tp.second].size()!=tp.first)continue;

        if(tp.first==0)stop(0);

        //cout<<"! forced "<<tp.second<<endl;

        solved[tp.second]=1;

        if(tp.second<=n)LHS+=inp[*adj[tp.second].begin()].add;
        else RHS+=inp[*adj[tp.second].begin()].add;

        cut_edge(*adj[tp.second].begin());
    }

    if(LHS<=total/2)can[LHS]=1;
    if(RHS<=total/2)can[RHS]=1;

    //cout<<LHS<<" "<<RHS<<endl;

    //cycles of even length
    for(int i=1;i<=2*n;i++)
        if(solved[i]==0)
        {
            int sum[2]={0,0};

            int pos=i,where=0;

            while(adj[pos].size())
            {
                solved[pos]=1;
                int edge=*adj[pos].begin();

                sum[where]+=inp[edge].add;
                where=!where;

                adj[inp[edge].l].erase(edge);
                adj[inp[edge].r].erase(edge);

                pos=inp[edge].l+inp[edge].r-pos;
            }

            //cout<<"pick "<<sum[0]<<" "<<sum[1]<<endl;

            can=(can<<sum[0])|(can<<sum[1]);
            /*
            for(int j=0;j<=total;j++)
                if(can[j])cout<<j<<" ";cout<<endl;
            */
        }

    for(int i=0;i<=total/2;i++)
        if(can[i]&&abs(total-2*i)<=k)stop(1);

    stop(0);
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:71:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(adj[tp.second].size()!=tp.first)continue;
            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
tug.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
tug.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&inp[i].l,&inp[i].r,&inp[i].add);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29