Submission #429492

#	Time	Username	Problem	Language	Result	Execution time	Memory
429492		Amylopectin	Friend (IOI14_friend)	C++14	100 / 100	124 ms	15120 KiB

friend

#include <iostream>
#include <stdio.h>
#include <vector>
#include "friend.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 2e5 + 10;
vector <vector<int> > pa,chi;
int nn,econ[mxn] = {},chv[mxn] = {},sev[mxn] = {},ru,cw[mxn] = {},rep[mxn] = {};
bool sta[mxn] = {};
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
//gli[mxn] = {},u[mxn] = {},ra[mxn] = {},gr[mxn] = {},
//int figr(int l)
//{
//    int cn = l,f;
//    while(gr[cn] != cn)
//    {
//        cn = gr[cn];
//    }
//    while(gr[l] != l)
//    {
//        f = gr[l];
//        gr[l] = cn;
//        l = f;
//    }
//    return cn;
//}
//int mer(int l,int r)
//{
//    int pl,pr;
//    pl = figr(l);
//    pr = figr(r);
//}
//int re(int la,int su)
//{
//    int fn,i,j,cu[mxn] = {};
//    ma = fima(su,ma);
//    for(i=0; i<nn; i++)
//    {
//        cu[i] = u[i];
//    }
//    for(i=0; i<nn; i++)
//    {
//        if(cu[i] == 0)
//        {
//            for(j=0; j<pa[i].size(); j++)
//            {
//                u[pa[i][j]] = 1;
//            }
//            u[i] = 1;
//            re(la+1,su + econ[i]);
//            for(j=0; j<nn; j++)
//            {
//                u[j] = cu[j];
//            }
//        }
//    }
//    return 0;
//}
//int re2(int cn,int be);
int rech(int cn);

int re3(int cn)
{
    int i,fn;
    for(i=0; i<pa[cn].size(); i++)
    {
        fn = pa[cn][i];
        rech(fn);
        sev[cn] += chv[fn];
        chv[cn] += sev[fn];
    }
//    if(sev[cn] < chv[cn])
//    {
//        sev[cn] = chv[cn];
//    }
    return 0;
}
int rech(int cn)
{
    int i,fn,cva,cma;
    if(chi[cn].size() == 0)
    {
        sev[cn] = econ[rep[cn]];
        re3(cn);
        if(sev[cn] < chv[cn])
        {
            sev[cn] = chv[cn];
        }
        return 0;
    }
    re3(cn);
    if(sta[cn] == 1)
    {
        for(i=0; i<chi[cn].size(); i++)
        {
            fn = chi[cn][i];
            rech(fn);
//            if(sta[cn] == 1)
//            {
                sev[cn] += sev[fn];
                chv[cn] += chv[fn];
//            }
//            else
//            {
//                sev[cn] += fima(sev[fn] + )
//            }
        }
    }
    else
    {
        cva = 0;
        cma = -1;
        for(i=0; i<chi[cn].size(); i++)
        {
            fn = chi[cn][i];
            rech(fn);
            cva += chv[fn];
        }
        chv[cn] += cva;
        for(i=0; i<chi[cn].size(); i++)
        {
            fn = chi[cn][i];
            cma = fima(cma,cva - chv[fn] + sev[fn]);
        }
        sev[cn] += cma;
    }
    if(sev[cn] < chv[cn])
    {
        sev[cn] = chv[cn];
    }
//    if(sev[cn] < chv[cn] && hon == 1)
//    {
//        sev[cn] = chv[cn];
//    }
    return 0;
}
//int re2(int cn,int be)
//{
//    int i,fn;
//    if(cn < nn)
//        sev[cn] = econ[cn];
//    for(i=0; i<pa[cn].size(); i++)
//    {
//        fn = pa[cn][i];
//        if(fn == be)
//        {
//            continue;
//        }
//        re2(fn,cn);
//        sev[cn] += chv[fn];
//        chv[cn] += sev[fn];
//    }
//    if(chv[cn] > sev[cn])
//    {
//        sev[cn] = chv[cn];
//    }
//    return 0;
//}
int findSample(int n,int conf[],int ho[],int prot[])
{
	int i,j,ans,cn,fn;
	nn = n;
	ru = n;
	for(i=0; i<n; i++)
	{
        econ[i] = conf[i];
//        gr[i] = i;
        cw[i] = i;
        rep[i] = i;
        pa.push_back({});
        chi.push_back({});
//        ma = fima(ma,conf[i]);
	}
	for(i=1; i<n; i++)
	{
//        ho[i] = gr[ho[i]];
        if(prot[i] == 0)
        {
            pa[cw[ho[i]]].push_back(i);
//            pa[i].push_back(cw[ho[i]]);
        }
        else if(prot[i] == 1)
        {
//            cn = ho[i];
//            gr[i] = gr[ho[i]];
            chi[cw[ho[i]]].push_back(i);
            chi[cw[ho[i]]].push_back(ru);
            sta[cw[ho[i]]] = 1;
            rep[ru] = ho[i];
            cw[ho[i]] = ru;
            pa.push_back({});
            chi.push_back({});
            ru ++;
//            econ[cn] += econ[i];
//            gr[i] = ho[i];
//            for(j=0; j<pa[cn].size(); j++)
//            {
//                fn = pa[cn][j];
//                pa[i].push_back(fn);
//                pa[fn].push_back(i);
//            }
        }
        else
        {
//            gr[i] = gr[ho[i]];
            chi[cw[ho[i]]].push_back(i);
            chi[cw[ho[i]]].push_back(ru);
            sta[cw[ho[i]]] = 0;
            rep[ru] = ho[i];
            cw[ho[i]] = ru;
            pa.push_back({});
            chi.push_back({});
            ru ++;
//            cn = ho[i];
//            econ[cn] = fima(econ[cn],econ[i]);
//            gr[i] = ho[i];

//            for(j=0; j<pa[cn].size(); j++)
//            {
//                fn = pa[cn][j];
//                pa[i].push_back(fn);
//                pa[fn].push_back(i);
//            }
//            pa[cn].push_back(i);
//            pa[i].push_back(cn);
        }
	}
	rech(0);
	ans = fima(sev[0],chv[0]);
//	re(0,0);
	return ans;
}
//int main()

//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message (stderr)

friend.cpp: In function 'int re3(int)':
friend.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(i=0; i<pa[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~
friend.cpp: In function 'int rech(int)':
friend.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(i=0; i<chi[cn].size(); i++)
      |                  ~^~~~~~~~~~~~~~~
friend.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(i=0; i<chi[cn].size(); i++)
      |                  ~^~~~~~~~~~~~~~~
friend.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(i=0; i<chi[cn].size(); i++)
      |                  ~^~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:167:8: warning: unused variable 'j' [-Wunused-variable]
  167 |  int i,j,ans,cn,fn;
      |        ^
friend.cpp:167:14: warning: unused variable 'cn' [-Wunused-variable]
  167 |  int i,j,ans,cn,fn;
      |              ^~
friend.cpp:167:17: warning: unused variable 'fn' [-Wunused-variable]
  167 |  int i,j,ans,cn,fn;
      |                 ^~

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31