oj.uz

Submission #625104

# Submission time Handle Problem Language Result Execution time Memory
625104 2022-08-09T11:14:11 Z Dremix10 Connecting Supertrees (IOI20_supertrees) C++17
56 / 100
 221 ms 28864 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<x<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pv(x) {}
#endif
const ll INF = 2e18+5;
const int MOD = 1e9+7;
const int N = 1005;

vector<vector<int> > ans;
int v[N];
vector<vector<vector<int> > > a(N,vector<vector<int> >(3,vector<int>()));

int nn;
bool flag = true;

vector<int> par(N),siz(N,1);
vector<vector<int> > g(N);
vector<int> s(N),e(N);

int find(int x){
    return (par[x] == x) ? x : par[x] = find(par[x]);
}
bool go = false;
bool join(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return false;
    if(g[y].size() > g[x].size())swap(x,y);
    siz[x] += siz[y];
    par[y] = x;
    for(auto v : g[y])g[x].push_back(v);
    g[y].clear();
    p2(s[x],e[x])
    p2(s[y],e[y])
    if(go)
        ans[e[x]][s[y]] = ans[s[y]][e[x]] = 1;
    e[x] = e[y];
    return true;

}

int construct(std::vector<std::vector<int>> p) {
	int i,j,n = p.size();
    ans.assign(n,vector<int>(n,0)); 
    for(i=0;i<n;i++){
        g[i].push_back(i);
        for(j=0;j<n;j++){
            if(i==j)continue;
            if(p[i][j] == 3)return 0;
            a[i][p[i][j]].push_back(j);
        }
    }

    iota(all(par),0);
    iota(all(s),0);
    iota(all(e),0);
    
    for(i=0;i<n;i++){
        if(v[i]){
            continue;
        }
        //vector<int> chk;
        //chk.push_back(i);
        int x = i;
        v[i] = true;
        for(auto j : a[i][1]){
            join(i,j);
            p2(i,j)
            //chk.push_back(j);    
            ans[x][j] = ans[j][x] = 1;
            x = j;

            v[j] = true;
        }
        s[find(i)] = i;
        e[find(i)] = i;
        for(int k=0;k<n;k++){
            bool ok = true;
            int need = p[i][k];
            for(auto j : g[find(i)]){
                if(j == k)continue;
                if(p[j][k] != need){
                    ok = false;
                    break;
                }
            }
            if(!ok){
                flag = false;
                break;
            }
        }

    }
    if(!flag)return 0;
    fill(all(siz),1);
    go = true;
    for(i=0;i<n;i++){
        for(auto x : a[i][2]){
            if(find(i) == find(x))continue;
            for(auto v1 : g[find(x)]){
                if(p[i][v1] != 2){
                    flag = false;
                    break;
                }
            }
            if(!flag)break;
            //ans[i][x] = ans[x][i] = 1;
            join(i,x);
            p2(i,x)
        }
    }

    for(i=0;i<n;i++){
        if(siz[find(i)] == 2)flag = false;
    }

    for(i=0;i<n;i++){
        int x = s[find(i)];
        int y = e[find(i)];
        if(siz[find(i)] == 1)continue;
        ans[x][y] = ans[y][x] = 1;
    }

    if(!flag)return 0;
    build(ans);
    return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 169 ms 26144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 169 ms 26144 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 8 ms 1492 KB Output is correct
13 Correct 177 ms 26136 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 1124 KB Output is correct
17 Correct 86 ms 17120 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 43 ms 6964 KB Output is correct
21 Correct 221 ms 26792 KB Output is correct
22 Correct 181 ms 26172 KB Output is correct
23 Correct 181 ms 26236 KB Output is correct
24 Correct 187 ms 26332 KB Output is correct
25 Correct 81 ms 16972 KB Output is correct
26 Correct 83 ms 16284 KB Output is correct
27 Correct 188 ms 28188 KB Output is correct
28 Correct 179 ms 26204 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 195 ms 26152 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 8 ms 1492 KB Output is correct
13 Correct 190 ms 26256 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 8 ms 1492 KB Answer gives possible 1 while actual possible 0
17 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 48 ms 6940 KB Output is correct
5 Correct 173 ms 26788 KB Output is correct
6 Correct 176 ms 26280 KB Output is correct
7 Correct 177 ms 26188 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 46 ms 6988 KB Output is correct
10 Correct 183 ms 26792 KB Output is correct
11 Correct 183 ms 26236 KB Output is correct
12 Correct 185 ms 28184 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 48 ms 7344 KB Output is correct
17 Correct 181 ms 28864 KB Output is correct
18 Correct 178 ms 28816 KB Output is correct
19 Correct 183 ms 28308 KB Output is correct
20 Correct 174 ms 28236 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 169 ms 26144 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 8 ms 1492 KB Output is correct
13 Correct 177 ms 26136 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 1124 KB Output is correct
17 Correct 86 ms 17120 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 43 ms 6964 KB Output is correct
21 Correct 221 ms 26792 KB Output is correct
22 Correct 181 ms 26172 KB Output is correct
23 Correct 181 ms 26236 KB Output is correct
24 Correct 187 ms 26332 KB Output is correct
25 Correct 81 ms 16972 KB Output is correct
26 Correct 83 ms 16284 KB Output is correct
27 Correct 188 ms 28188 KB Output is correct
28 Correct 179 ms 26204 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 8 ms 1492 KB Output is correct
37 Correct 195 ms 26152 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 8 ms 1492 KB Output is correct
41 Correct 190 ms 26256 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Incorrect 8 ms 1492 KB Answer gives possible 1 while actual possible 0
45 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 169 ms 26144 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 8 ms 1492 KB Output is correct
13 Correct 177 ms 26136 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 1124 KB Output is correct
17 Correct 86 ms 17120 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 43 ms 6964 KB Output is correct
21 Correct 221 ms 26792 KB Output is correct
22 Correct 181 ms 26172 KB Output is correct
23 Correct 181 ms 26236 KB Output is correct
24 Correct 187 ms 26332 KB Output is correct
25 Correct 81 ms 16972 KB Output is correct
26 Correct 83 ms 16284 KB Output is correct
27 Correct 188 ms 28188 KB Output is correct
28 Correct 179 ms 26204 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 8 ms 1492 KB Output is correct
37 Correct 195 ms 26152 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 8 ms 1492 KB Output is correct
41 Correct 190 ms 26256 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Incorrect 8 ms 1492 KB Answer gives possible 1 while actual possible 0
45 Halted 0 ms 0 KB -