oj.uz

Submission #300665

# Submission time Handle Problem Language Result Execution time Memory
300665 2020-09-17T11:24:39 Z Odavey Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 285 ms 26488 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#include                "supertrees.h"
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

int n;

//void build(vector<vector<int> > b){
//    for(auto& v : b){
//        for(int x : v){
//            cout << x << ' ';
//        }
//        cout << endl;
//    }
//    cout << endl;
//    return;
//}

struct link{
    link* par;
    int id;
    int m_id;
};

link* find_set(link* at){
    if(at == at->par){
        return at;
    }else{
        return at->par = find_set(at->par);
    }
}

void union_set(link* A, link* B){
    link* a = find_set(A);
    link* b = find_set(B);
    if(a == b){
        return;
    }
    a->par = b;
    return;
}

vector<int> adj[MX_N];
vector<int> familes[MX_N];

link* G[MX_N];

int construct(vector<vector<int> > p){
    n = p.size();
    auto res = p;
    for(auto& v : res){
        for(int& x : v){
            x = 0;
        }
    }
    for(int i=0;i<n;++i){
        G[i] = new link;
        G[i]->id = i;
        G[i]->par = G[i];
    }
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            if(p[i][j] == 1 || p[i][j] == 2){
                adj[i].pb(j);
                adj[j].pb(i);
                union_set(G[i], G[j]);
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            if(p[i][j] == 0){
                if(find_set(G[i]) == find_set(G[j])){
                    return 0;
                }
            }
        }
    }
    for(int i=0;i<n;++i){
        G[i]->m_id = familes[find_set(G[i])->id].size();
        familes[find_set(G[i])->id].pb(i);
    }
    for(int i=0;i<n;++i){
        G[i]->par = G[i];
    }
    for(int f=0;f<n;++f){
        if(familes[f].size() <= 1){
            continue;
        }
        vector<int>& group = familes[f];
        int m = group.size();
        for(int i=0;i<m;++i){
            for(int to : adj[group[i]]){
                if(p[i][to] == 1){
                    union_set(G[i], G[to]);
                }
            }
        }
        vector<int> lots[m];
        for(int i=0;i<m;++i){
            lots[find_set(G[i])->m_id].pb(group[i]);
        }
        vector<int> circle;
        vector<vector<int> > chains;
        for(int i=0;i<m;++i){
            if(lots[i].size() == 0){
                continue;
            }else if(lots[i].size() == 1){
                circle.pb(lots[i][0]);
            }else{
                chains.pb(lots[i]);
            }
        }
        for(auto& chain : chains){
            for(int i=1;i<(int)chain.size();++i){
                res[chain[i]][chain[i-1]] = 1;
                res[chain[i-1]][chain[i]] = 1;
            }
        }
        for(int i=1;i<(int)chains.size();++i){
            res[chains[i][0]][chains[i-1][0]] = 1;
            res[chains[i-1][0]][chains[i][0]] = 1;
        }
        for(int i=1;i<(int)circle.size();++i){
            res[circle[i]][circle[i-1]] = 1;
            res[circle[i-1]][circle[i]] = 1;
        }
        if(circle.size() == 0){
            continue;
        }else if(chains.size() == 0){
            if(circle.size() == 2){
                return 0;
            }
            res[circle[0]][circle[circle.size()-1]] = 1;
            res[circle[circle.size()-1]][circle[0]] = 1;
        }else{
            res[circle[0]][chains[0][0]] = 1;
            res[chains[0][0]][circle[0]] = 1;
            res[circle[circle.size()-1]][chains[chains.size()-1][0]] = 1;
            res[chains[chains.size()-1][0]][circle[circle.size()-1]] = 1;
        }
    }
    build(res);
    return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 17 ms 1664 KB Output is correct
7 Correct 285 ms 26488 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 17 ms 1664 KB Output is correct
7 Correct 285 ms 26488 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 12 ms 1536 KB Output is correct
13 Correct 248 ms 22392 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 6 ms 1152 KB Output is correct
17 Correct 128 ms 15224 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Runtime error 34 ms 7164 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 10 ms 1408 KB Output is correct
9 Correct 245 ms 22520 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 11 ms 1664 KB Output is correct
13 Correct 259 ms 26488 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 6 ms 1152 KB Output is correct
17 Correct 126 ms 15224 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Incorrect 63 ms 6136 KB Too few ways to get from 0 to 5, should be 2 found 1
22 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Runtime error 34 ms 7168 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 17 ms 1664 KB Output is correct
7 Correct 285 ms 26488 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 12 ms 1536 KB Output is correct
13 Correct 248 ms 22392 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 6 ms 1152 KB Output is correct
17 Correct 128 ms 15224 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Runtime error 34 ms 7164 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 17 ms 1664 KB Output is correct
7 Correct 285 ms 26488 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 12 ms 1536 KB Output is correct
13 Correct 248 ms 22392 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 6 ms 1152 KB Output is correct
17 Correct 128 ms 15224 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Runtime error 34 ms 7164 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -