Submission #298307

#	Time	Username	Problem	Language	Result	Execution time	Memory
298307		arayi	Split the Attractions (IOI19_split)	C++17	18 / 100	134 ms	10864 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];
bool col[N];
void dfss(int v)
{
    col[v] = 1;
    sz[v] = 1;
    for(auto p : g[v])
    {
        if(col[p]) continue;
        dfss(p);
        sz[v] += sz[p];
    }
}
void dfs0(int v)
{
    if(mn == 0) return;
    mn--;
    pat[v] = fp[1];
    for(auto p : g[v])
    {
        if(sz[p] > sz[v] || pat[p]) continue;
        dfs0(p);
    }
}
void dfs(int v)
{
    if(mj == 0) return;
    mj--;
    pat[v] = fp[2];
    for(auto p : g[v])
    {
        if(sz[p] > sz[v] || 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];
	for (int i = 0; i < p.size(); i++)
	{
	    g[p[i]].ad(q[i]);
	    g[q[i]].ad(p[i]);
	}
	int i1 = 0;
	for (int i = 0; i < n; i++) if(g[i].size() == 1) i1 = i;
    dfs0(i1);
    for (int i = 0; i < n; i++)
    {
        if(!pat[i])
        {
            dfs(i);
            break;
        }
    }
    for (int i = 0; i < n; i++) if(!pat[i]) pat[i] = fp[3];

	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:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~

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