oj.uz

Submission #370879

# Submission time Handle Problem Language Result Execution time Memory
370879 2021-02-24T23:41:47 Z Ozy Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1000 ms 1734088 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " " <<  a << endl
#define nl "\n"

lli n,ult,a,b,c,d;
lli padre[1002],grupo[1002],visitados[1002],inicios[1002],finales[1002],cant[1002];
bool res;
vector<lli> cabezas;

void procesa(lli act) {
    if (padre[act] != act) {
        procesa(padre[act]);
        padre[act] = ult;
    }
    else ult = act;
}

void calcula(lli act) {
    if (grupo[act] != act) {
        calcula(grupo[act]);
        grupo[act] = ult;
    }
    else ult = act;
}

int construct(std::vector<std::vector<int>> p) {

	res = true;
	n = p.size();
	vector<vector<int> > puentes(n, vector<int> (n, 0));

	rep(i,0,n-1) {
        rep(j,0,n-1){
            if (visitados[j] == 1) continue;
            if (i == j) continue;

            if (p[i][j] != p[j][i]) res = false;
            if (p[i][j] == 3) res = false;
            if (res == false) return 0;

            if (p[i][j] == 1) {
                padre[j] = i;
                puentes[i][j] = 1;
                puentes[j][i] = 1;
                visitados[j] = 1;
            }
        }
	}


	rep(i,0,n-1) {

	    if (padre[i] != i) continue;

        rep(j,0,n-1){
            if (i == j) continue;
            if (padre[i] != i) continue;
            if (visitados[j] == 2) continue;


            if (p[i][j] == 2) {
                grupo[j] = i;
                visitados[j]=2;
            }
        }
	}

	rep(i,0,n-1) {
	    rep(j,0,n-1) {

            procesa(i);
            a = ult;
            procesa(j);
            b = ult;

            calcula(a);
            c = ult;
            calcula(b);
            d = ult;


            if (p[i][j] == 0){
                if (a != b && c != d) continue;
                else res = false;
            }
            else if (p[i][j] == 1){
                if (a == b && c == d) continue;
                else res = false;
            }
            else {
                if (a != b && c == d) continue;
                else res = false;
            }

            if (!res) return 0;
	    }
	}

	rep(i,0,n-1) {
        if (padre[i] == i) {

            calcula(i);

            if (cant[ult] == 0) {
                inicios[ult] = i;
                finales[ult] = i;
                cant[ult] = 1;
            }
            else {
                puentes[ult][finales[ult]] = 1;
                puentes[finales[ult]][ult] = 1;

                finales[ult] = i;
                cant[ult]++;
            }

        }
	}

	rep(i,0,n-1) {
        if (cant[i] == 2) return 0;

        if (cant[i] > 2) {
            puentes[finales[i]][inicios[i]] = 1;
            puentes[inicios[i]][finales[i]] = 1;
        }
	}

	build(puentes);
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 1203 ms 1734088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 1203 ms 1734088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 1203 ms 1734088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 1203 ms 1734088 KB Time limit exceeded
3 Halted 0 ms 0 KB -