oj.uz

Submission #150834

# Submission time Handle Problem Language Result Execution time Memory
150834 2019-09-01T08:58:50 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 7 ms 768 KB 
#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 205;

int dsu[N];

int trace(int u)
{
	return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
}

void connect(int u, int v)
{
	if ((u = trace(u)) == (v = trace(v)))
		return;
	if (dsu[u] > dsu[v])
		swap(u, v);
	int tmp = dsu[v];
	dsu[u] += dsu[v];
	dsu[v] = u;
}

int FindBase(int N){
    vector<vector<int> > s, t, de;
    vector<int> la;
    for(int i = 0; i < N; i++)
	{
		dsu[i] = -1;
		s.push_back({i});
	}
 
    while(s.size() > 1){
        for(int i = 1; i < s.size(); i += 2){
			int u = -1;
			bool chk = trace(s[i - 1][0]) == trace(s[i][0]);
			if (!chk)
				u = CollectRelics(s[i - 1][0], s[i][0]);
            if(chk || u > -1){
				connect(s[i - 1][0], s[i][0]);
				if (u > -1)
					connect(s[i - 1][0], u);
                for(int& x : s[i - 1])
                    s[i].push_back(x);
                t.push_back(s[i]);
            } else {
                de.push_back(s[i - 1]);
                de.push_back(s[i]);
            }
        }

        if(s.size() & 1){
            de.push_back(s.back());
            la = s.back();
        }

        swap(s, t);
        t.clear();
    }
 
    int sz = 0;
    
    if(s.empty()) s.push_back(la);
    else sz = s[0].size();
    if(s[0].empty()) return -1;

    int res = 0;

    for(int i = 1; i < s[0].size(); i++){
        res = max(res, CollectRelics(s[0][i], s[0][0]));
    }

    for(auto& x : de){
        int rrr = CollectRelics(x[0], s[0][0]);
        if(rrr != -1){
            res = max(res, rrr);
            for(int i = 1; i < x.size(); i++){
                rrr = CollectRelics(x[i], s[0][0]);
                res = max(res, rrr);
            }
            sz += x.size();
        }
    }
    if(sz > N / 2) return res;
    return -1;
}

Compilation message

lokahia.cpp: In function 'void connect(int, int)':
lokahia.cpp:20:6: warning: unused variable 'tmp' [-Wunused-variable]
  int tmp = dsu[v];
      ^~~
lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:35:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < s.size(); i += 2){
                        ~~^~~~~~~~~~
lokahia.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < s[0].size(); i++){
                    ~~^~~~~~~~~~~~~
lokahia.cpp:78:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 1; i < x.size(); i++){
                            ~~^~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Correct : C = 177
2 Incorrect 7 ms 640 KB Wrong
3 Correct 7 ms 640 KB Correct : C = 117
4 Incorrect 5 ms 512 KB Wrong
5 Correct 5 ms 512 KB Correct : C = 6
6 Correct 6 ms 640 KB Correct : C = 297
7 Incorrect 6 ms 640 KB Wrong
8 Incorrect 6 ms 640 KB Wrong
9 Correct 6 ms 640 KB Correct : C = 299
10 Correct 7 ms 640 KB Correct : C = 296
11 Correct 6 ms 520 KB Correct : C = 179
12 Correct 5 ms 512 KB Correct : C = 0
13 Correct 6 ms 640 KB Correct : C = 177
14 Correct 6 ms 768 KB Correct : C = 299
15 Correct 6 ms 512 KB Correct : C = 179
16 Correct 7 ms 640 KB Correct : C = 297
17 Correct 6 ms 640 KB Correct : C = 60
18 Correct 6 ms 640 KB Correct : C = 299
19 Correct 5 ms 640 KB Correct : C = 177
20 Incorrect 7 ms 640 KB Wrong
21 Correct 6 ms 640 KB Correct : C = 100
22 Correct 6 ms 640 KB Correct : C = 297
23 Incorrect 5 ms 640 KB Wrong
24 Correct 6 ms 512 KB Correct : C = 179
25 Correct 6 ms 640 KB Correct : C = 299
26 Correct 6 ms 640 KB Correct : C = 177
27 Correct 7 ms 640 KB Correct : C = 105