oj.uz

Submission #864720

# Submission time Handle Problem Language Result Execution time Memory
864720 2023-10-23T13:43:57 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
0 / 100
 125 ms 223784 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 42 ms 15956 KB Output is correct
7 Runtime error 125 ms 223784 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Incorrect 2 ms 12380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Incorrect 2 ms 12380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Incorrect 2 ms 12140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Incorrect 2 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 3 ms 12372 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Incorrect 2 ms 12296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 42 ms 15956 KB Output is correct
7 Runtime error 125 ms 223784 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -