oj.uz

Submission #471284

# Submission time Handle Problem Language Result Execution time Memory
471284 2021-09-08T07:13:56 Z Cross_Ratio Comparing Plants (IOI20_plants) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

struct UnionFind {
    vector<int> root;
    void init(int N) {
        root.clear();
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int c) {
        if(root[c] < 0) return c;
        int r = Find(root[c]);
        root[c] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(x == y) return;
        if(root[x] > root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int K, N;
vector<int> C;
vector<int> D;
vector<int> R;
UnionFind UF1, UF2;
void init(int k, vector<int> r) {
    R = r;
    N = r.size();
    K = k;
    int i, j;
    if(k == 2) {
        UF1.init(N);
        UF2.init(N);
        for(i=0;i<N;i++) {
            if(r[i]) {
                UF1.Merge(i, (i + 1) % N);
            }
            else UF2.Merge(i, (i + 1) % N);
        }
    }
}

int compare_plants(int x, int y) {
	if(UF1.Find(x)==UF1.Find(y)) {
        int check = 1;
        if(x < y) {
            swap(x, y);
            check = -1;
        }
        if(UF1.Find(x)==UF1.Find(0)&&UF1.Find(x)==UF1.Find(N-1)&&UF2.Find(0)!=UF2.Find(N-1)) {
            return -check;
        }
        else return check;
	}
	if(UF2.Find(x) == UF2.Find(y)) {
        int check = 1;
        if(x < y) {
            swap(x, y);
            check = -1;
        }
        if(UF2.Find(x)==UF2.Find(0)&&UF2.Find(x)==UF2.Find(N-1)&&UF1.Find(0)!=UF1.Find(N-1)) {
            return check;
        }
        else return -check;
	}
	return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:36:12: warning: unused variable 'j' [-Wunused-variable]
   36 |     int i, j;
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -