Submission #316887

#	Time	Username	Problem	Language	Result	Execution time	Memory
316887		lukasanarski	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	278 ms	22264 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1001;
bool used[N];
vector<vector<int> > b;
int comp[N], line[N];
int construct(vector<vector<int> > p) {
    int n = p.size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(p[i][j] == 3) {
                return 0;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        vector<int> v;
        v.resize(n);
        b.push_back(v);
    }
    //cout<<"Came!"<<endl;
    for(int i = 0; i < n; i++) {
        if(used[i]) {
            continue;
        }
        //cout<<"I: "<<i<<endl;
        vector<int> cycle;
        deque<int> D;
        D.push_back(i);
        while(D.size()) {
            int x = D.front();
            D.pop_front();
            if(used[x]) {
                continue;
            }
            //cout<<"X: "<<x<<endl;
            vector<int> curr;
            deque<int> G;
            G.push_back(x);
            cycle.push_back(x);
            while(G.size()) {
                int y = G.front();
                G.pop_front();
                if(used[y]) {
                    continue;
                }
                //cout<<"Y: "<<y<<endl;
                used[y] = true;
                comp[y] = i;
                line[y] = x;
                curr.push_back(y);
                for(int j = 0; j < n; j++) {
                    if(p[y][j] == 1) {
                        G.push_back(j);
                    } else if(p[y][j] == 2) {
                        D.push_back(j);
                    }
                }
            }
            if(curr.size() > 1) {
                for(int j = 0; j < (int)curr.size() - 1; j++) {
                    b[curr[j]][curr[j + 1]] = 1;
                    b[curr[j + 1]][curr[j]] = 1;
                }
            }
        }
        if(cycle.size() == 2) {
            return 0;
        }
        if(cycle.size() == 1) {
            continue;
        }
        for(int j = 0; j < (int)cycle.size() - 1; j++) {
            b[cycle[j]][cycle[j + 1]] = 1;
            b[cycle[j + 1]][cycle[j]] = 1;
        }
        b[cycle[0]][cycle[(int)cycle.size() - 1]] = 1;
        b[cycle[(int)cycle.size() - 1]][cycle[0]] = 1;
    }
    /*cout<<"Came!"<<endl;
    cout<<"Lines: "<<endl;
    for(int i = 0; i < n; i++) {
        cout<<line[i]<<" ";
    }
    cout<<endl;
    cout<<"Comps: "<<endl;
    for(int i = 0; i < n; i++) {
        cout<<comp[i]<<" ";
    }
    cout<<endl;*/
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(line[i] == line[j]) {
                if(p[i][j] != 1) {
                    return 0;
                }
            } else if(comp[i] == comp[j]) {
                if(p[i][j] != 2) {
                    return 0;
                }
            } else if(p[i][j] != 0) {
                return 0;
            }
        }
    }

    /*for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }*/

    build(b);
    return 1;
}

/*int main() {
    int n;
    cin>>n;
    vector<vector<int> > p(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int x;
            cin>>x;
            p[i].push_back(x);
        }
    }
    construct(p);

}*/

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4