Submission #298267

#	Time	Username	Problem	Language	Result	Execution time	Memory
298267		arayi	Split the Attractions (IOI19_split)	C++17	0 / 100	618 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define ad push_back
using namespace std;

const int N = 1e5 + 20;
int mn, mj;
int sz[N];
int fp[5];
vector <int> pat, g[N];
void dfss(int v, int par)
{
    sz[v] = 1;
    for(auto p : g[v])
    {
        if(p == par) continue;
        dfss(p, v);
        sz[v] += sz[p];
    }
}
void dfs0(int v)
{
    if(mj == 0) return;
    mj--;
    pat[v] = fp[2];
    for(auto p : g[v])
    {
        if(sz[p] > sz[v]) continue;
        dfs0(p);
    }
}
void dfs(int v)
{
    if(mn == 0) return;
    mn--;
    pat[v] = fp[1];
    for(auto p : g[v])
    {
        if(pat[p]) continue;
        dfs(p);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	mn = min(a, min(b, c));
	mj = a + b + c - mn - max(a, max(b, c));
	for (int i = 0; i < n; i++) pat.ad(0);
	if(mn == a) fp[1] = 1;
	if(mn == b) fp[1] = 2;
	if(mn == c) fp[1]= 3;
	if(mj == a) fp[2] = 1;
	else if(mj == b) fp[2] = 2;
	else fp[2] = 3;
	fp[3] = 6 - fp[1] - fp[2];
	//cout << mn << " " << mj << endl << fp[1] << " " << fp[2] << endl;
	for (int i = 0; i < p.size(); i++)
	{
	    g[p[i]].ad(q[i]);
	    g[q[i]].ad(p[i]);
	}
	dfss(0, 0);
	for (int i = 0; i < n; i++)
	{
	    if(sz[i] >= mj && n - sz[i] >= mn)
        {
            dfs0(i);
            dfs(0);
            for (int j = 0; j < n; j++)
                if(!pat[j]) pat[j] = fp[3];
            return pat;
        }
	}
	return pat;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36