oj.uz

Submission #331769

# Submission time Handle Problem Language Result Execution time Memory
331769 2020-11-30T02:39:46 Z thecodingwizard Izlet (COI19_izlet) C++11
18 / 100
 591 ms 53740 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 3000
int n; 
int input[maxn][maxn];

vector<int> nodes; // stores nodes remaining after 1's are compressed
map<int, vector<int>> nodesInOneComponent;
void compressOnes() {
    vector<bool> done(n, 0);
    F0R(i, n) {
        if (done[i]) continue;
        nodes.pb(i);
        done[i] = true;
        F0R(j, n) {
            if (input[i][j] == 1 && j != i) {
                nodesInOneComponent[i].pb(j);
                done[j] = true;
            }
        }
    }
}

void findTwos() {

}

int assignedColor[maxn];
vector<ii> outputEdges;

void buildTree() {
    assignedColor[nodes[0]] = 1;
    FOR(i, 1, nodes.size()) {
        outputEdges.emplace_back(nodes[0], nodes[i]);
        assignedColor[nodes[i]] = 2;
    }
}

void decompressOnes() {
    for (int x : nodes) {
        for (int y : nodesInOneComponent[x]) {
            outputEdges.pb(mp(x, y));
            assignedColor[y] = assignedColor[x];
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int subtask; cin >> subtask; assert(subtask == 1);
    cin >> n;
    F0R(i, n) {
        F0R(j, n) {
            cin >> input[i][j];
        }
    }

    compressOnes();

    findTwos();

    buildTree();

    decompressOnes();

    F0R(i, n) cout << assignedColor[i] << " ";
    cout << endl;
    for (auto x : outputEdges) cout << x.f+1 << " " << x.s+1 << endl;

    return 0;
}

Compilation message

izlet.cpp: In function 'void buildTree()':
izlet.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(i, a, b) for (int i = a; i < b; i++)
......
   46 |     FOR(i, 1, nodes.size()) {
      |         ~~~~~~~~~~~~~~~~~~              
izlet.cpp:46:5: note: in expansion of macro 'FOR'
   46 |     FOR(i, 1, nodes.size()) {
      |     ^~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 581 ms 53544 KB Output is correct
3 Correct 591 ms 53740 KB Output is correct
4 Correct 557 ms 53416 KB Output is correct
5 Correct 564 ms 53420 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 581 ms 53544 KB Output is correct
3 Correct 591 ms 53740 KB Output is correct
4 Correct 557 ms 53416 KB Output is correct
5 Correct 564 ms 53420 KB Output is correct
6 Runtime error 3 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -