Submission #471284

#	Time	Username	Problem	Language	Result	Execution time	Memory
471284		Cross_Ratio	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	332 KiB

plants

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25