Submission #864720

#	Time	Username	Problem	Language	Result	Execution time	Memory
864720		andrei_boaca	Comparing Plants (IOI20_plants)	C++17	0 / 100	125 ms	223784 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
vector<int> muchii[200005];
int rel[5005][5005],n,bigger[200005],smaller[200005];
bool reach[5005][5005];
bool use[200005];
void dfs(int nod,int start)
{
    reach[start][nod]=1;
    for(int i:muchii[nod])
        if(!reach[start][i])
            dfs(i,start);
}
void init(int k, std::vector<int> r)
{
    n=r.size();
    queue<int> coada;
    for(int i=0;i<r.size();i++)
    {
        bigger[i]=r[i];
        smaller[i]=k-1-r[i];
        if(bigger[i]==0||smaller[i]==0)
            coada.push(i);
    }
    while(!coada.empty())
    {
        int nod=coada.front();
        use[nod]=1;
        coada.pop();
        for(int i=(nod+1)%n,cnt=1;cnt<k;cnt++,i=(i+1)%n)
            if(rel[nod][i]==0)
            {
                if(smaller[nod])
                {
                    smaller[nod]--;
                    rel[nod][i]=1;
                    muchii[i].push_back(nod);
                    rel[i][nod]=-1;
                    if((nod-i+n)%n<k)
                        bigger[i]--;
                }
                else
                {
                    bigger[nod]--;
                    muchii[nod].push_back(i);
                    rel[nod][i]=-1;
                    rel[i][nod]=1;
                    if((nod-i+n)%n<k)
                        smaller[i]--;
                }
                if(bigger[i]==0||smaller[i]==0)
                    if(!use[i])
                    {
                        use[i]=1;
                        coada.push(i);
                    }
            }
    }
    for(int i=0;i<n;i++)
        dfs(i,i);
}

int compare_plants(int x, int y) {
    if(reach[x][y])
        return -1;
    if(reach[y][x])
        return 1;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25