oj.uz

Submission #768433

# Submission time Handle Problem Language Result Execution time Memory
768433 2023-06-28T07:10:05 Z Khizri Connecting Supertrees (IOI20_supertrees) C++17
21 / 100
 183 ms 35056 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1e3+5;
int n,color[mxn],k,color2[mxn],sz,lst,arr[mxn][mxn];
vector<int>vt[mxn];
vector<int>vt2[mxn];
vector<vector<int>>p;
void dfs(int u){
    color[u]=k;
    sz++;
    for(int v:vt[u]){
        if(!color[v]){
            arr[u][v]=1;
            arr[v][u]=1;
            dfs(v);
        }
    }
}
void dfs2(int u){
    color2[u]=k;
    sz++;
    lst=u;
    for(int vv:vt2[u]){
        int v=color[vv];
        if(!color2[v]){
            arr[u][v]=1;
            arr[v][u]=1;
            dfs2(v);
        }
    }
}
int construct(vector<vector<int>> pp) {
    p=pp;
	n=p.size();
	for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==1){
                vt[i+1].pb(j+1);
                vt[j+1].pb(i+1);
            }
            else if(p[i][j]==2){
                vt2[i+1].pb(j+1);
                vt2[j+1].pb(i+1);
            }
            else if(p[i][j]==3){
                //cout<<"X1"<<endl;
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        if(!color[i]){
            k=i;
            sz=0;
            dfs(i);
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(color[i]==color[j]&&p[i-1][j-1]!=1){
                //cout<<i<<' '<<j<<endl;
                //cout<<"X2"<<endl;
                return 0;
            }
        }
	}
	vector<pii>v;
	for(int id=1;id<=n;id++){
        int i=color[id];
        if(color2[i]) continue;
        k=i;
        sz=0;
        dfs2(i);
        if(lst==i){
            color2[i]=0;
        }
        else{
            arr[i][lst]=1;
            arr[lst][i]=1;
            v.pb({i,lst});
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(color2[i]>0&&color2[i]==color2[j]&&p[i-1][j-1]!=2){
                //cout<<"X3"<<endl;
                return 0;
            }
        }
	}
	for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(p[i-1][j-1]==2){
                int a=color[i];
                int b=color[j];
                arr[a][b]=1;
                arr[b][a]=1;
            }
        }
	}
	vector<vector<int>>ans;
	for(int i=1;i<=n;i++){
        vector<int>vt;
        for(int j=1;j<=n;j++){
            vt.pb(arr[i][j]);
        }
        ans.pb(vt);
	}
	build(ans);
	return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 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 340 KB Output is correct
3 Correct 0 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 7 ms 2388 KB Output is correct
7 Correct 158 ms 34104 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 340 KB Output is correct
3 Correct 0 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 7 ms 2388 KB Output is correct
7 Correct 158 ms 34104 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 7 ms 1504 KB Output is correct
13 Correct 151 ms 27956 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 4 ms 1760 KB Output is correct
17 Correct 71 ms 20952 KB Output is correct
18 Correct 0 ms 352 KB Output is correct
19 Correct 1 ms 372 KB Output is correct
20 Correct 40 ms 9160 KB Output is correct
21 Correct 155 ms 32528 KB Output is correct
22 Correct 150 ms 31572 KB Output is correct
23 Correct 163 ms 34024 KB Output is correct
24 Correct 156 ms 28200 KB Output is correct
25 Correct 66 ms 18624 KB Output is correct
26 Correct 62 ms 17732 KB Output is correct
27 Correct 155 ms 35056 KB Output is correct
28 Correct 148 ms 28216 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 356 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 40 ms 9140 KB Output is correct
5 Correct 159 ms 32432 KB Output is correct
6 Correct 151 ms 31496 KB Output is correct
7 Correct 183 ms 34092 KB Output is correct
8 Incorrect 1 ms 340 KB Too many ways to get from 0 to 2, should be 2 found no less than 3
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 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 7 ms 2388 KB Output is correct
7 Correct 158 ms 34104 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 7 ms 1504 KB Output is correct
13 Correct 151 ms 27956 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 4 ms 1760 KB Output is correct
17 Correct 71 ms 20952 KB Output is correct
18 Correct 0 ms 352 KB Output is correct
19 Correct 1 ms 372 KB Output is correct
20 Correct 40 ms 9160 KB Output is correct
21 Correct 155 ms 32528 KB Output is correct
22 Correct 150 ms 31572 KB Output is correct
23 Correct 163 ms 34024 KB Output is correct
24 Correct 156 ms 28200 KB Output is correct
25 Correct 66 ms 18624 KB Output is correct
26 Correct 62 ms 17732 KB Output is correct
27 Correct 155 ms 35056 KB Output is correct
28 Correct 148 ms 28216 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Incorrect 0 ms 356 KB Answer gives possible 1 while actual possible 0
33 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 340 KB Output is correct
3 Correct 0 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 7 ms 2388 KB Output is correct
7 Correct 158 ms 34104 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 7 ms 1504 KB Output is correct
13 Correct 151 ms 27956 KB Output is correct
14 Correct 1 ms 352 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 4 ms 1760 KB Output is correct
17 Correct 71 ms 20952 KB Output is correct
18 Correct 0 ms 352 KB Output is correct
19 Correct 1 ms 372 KB Output is correct
20 Correct 40 ms 9160 KB Output is correct
21 Correct 155 ms 32528 KB Output is correct
22 Correct 150 ms 31572 KB Output is correct
23 Correct 163 ms 34024 KB Output is correct
24 Correct 156 ms 28200 KB Output is correct
25 Correct 66 ms 18624 KB Output is correct
26 Correct 62 ms 17732 KB Output is correct
27 Correct 155 ms 35056 KB Output is correct
28 Correct 148 ms 28216 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Incorrect 0 ms 356 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -