oj.uz

Submission #738027

# Submission time Handle Problem Language Result Execution time Memory
738027 2023-05-08T05:46:18 Z bobthebuilder Connecting Supertrees (IOI20_supertrees) C++17
56 / 100
 207 ms 24104 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define MNTO(x,y) x=min(x,y)
const int maxn=1e3+5;
namespace {
struct uf{
	int par[maxn];
	void init(int n){
		REP(i,n) par[i]=i;
	}
	int find(int u){
		if(par[u]==u) return u;
		return par[u]=find(par[u]);
	}
	void merge(int a,int b){
		a=find(a),b=find(b);
		if(a==b) return;
		par[a]=b;
	}
}a,b;

vector<int> cmp[maxn],ln[maxn];
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n,vector<int>(n));
	REP(i,n){
		REP(j,n){
			if(p[i][j]==3){
				return 0;
			}
		}
	}
	a.init(n),b.init(n);
	REP(i,n){
		REP(j,n){
			if(p[i][j]>=1){
				a.merge(i,j);
			}
		}
	}
	REP(i,n){
		cmp[a.find(i)].pb(i);
	}
	REP(i,n){
		for(int x:cmp[i]){
			for(int y:cmp[i]){
				if(p[x][y]==0){
					return 0;
				}
				if(p[x][y]==1){
					b.merge(x,y);
				}
			}
		}
		for(int x:cmp[i]){
			for(int y:cmp[i]){
				if(p[x][y]==2 and b.find(x)==b.find(y)){
					return 0;
				}
			}
		}
		vector<int> cyc;
		for(int x:cmp[i]){
			cyc.pb(b.find(x));
			ln[b.find(x)].pb(x);
		}
		SORT_UNIQUE(cyc);
		if(sz(cyc)>1){
			int k=sz(cyc);
			REP(j,k){
				ans[cyc[j]][cyc[(j+1)%k]]=ans[cyc[(j+1)%k]][cyc[j]]=1;
			}
		}
		for(int x:cmp[i]){
			int pv=-1;
			for(int y:ln[x]){
				if(pv!=-1) ans[pv][y]=ans[y][pv]=1; 
				pv=y;
			}
		}
	}
	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1292 KB Output is correct
7 Correct 184 ms 23964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1292 KB Output is correct
7 Correct 184 ms 23964 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 11 ms 1264 KB Output is correct
13 Correct 187 ms 24064 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 82 ms 14156 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 6304 KB Output is correct
21 Correct 180 ms 23980 KB Output is correct
22 Correct 178 ms 23992 KB Output is correct
23 Correct 204 ms 24016 KB Output is correct
24 Correct 168 ms 24064 KB Output is correct
25 Correct 73 ms 14132 KB Output is correct
26 Correct 71 ms 14116 KB Output is correct
27 Correct 193 ms 24036 KB Output is correct
28 Correct 174 ms 24012 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 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 352 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 244 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 57 ms 6208 KB Output is correct
5 Correct 174 ms 23996 KB Output is correct
6 Correct 187 ms 24080 KB Output is correct
7 Correct 188 ms 23976 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 42 ms 6312 KB Output is correct
10 Correct 174 ms 24040 KB Output is correct
11 Correct 168 ms 23988 KB Output is correct
12 Correct 188 ms 24104 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 46 ms 6308 KB Output is correct
17 Correct 187 ms 24052 KB Output is correct
18 Correct 171 ms 24012 KB Output is correct
19 Correct 207 ms 23980 KB Output is correct
20 Correct 205 ms 24044 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1292 KB Output is correct
7 Correct 184 ms 23964 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 11 ms 1264 KB Output is correct
13 Correct 187 ms 24064 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 82 ms 14156 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 6304 KB Output is correct
21 Correct 180 ms 23980 KB Output is correct
22 Correct 178 ms 23992 KB Output is correct
23 Correct 204 ms 24016 KB Output is correct
24 Correct 168 ms 24064 KB Output is correct
25 Correct 73 ms 14132 KB Output is correct
26 Correct 71 ms 14116 KB Output is correct
27 Correct 193 ms 24036 KB Output is correct
28 Correct 174 ms 24012 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Incorrect 1 ms 352 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 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1292 KB Output is correct
7 Correct 184 ms 23964 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 11 ms 1264 KB Output is correct
13 Correct 187 ms 24064 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 82 ms 14156 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 6304 KB Output is correct
21 Correct 180 ms 23980 KB Output is correct
22 Correct 178 ms 23992 KB Output is correct
23 Correct 204 ms 24016 KB Output is correct
24 Correct 168 ms 24064 KB Output is correct
25 Correct 73 ms 14132 KB Output is correct
26 Correct 71 ms 14116 KB Output is correct
27 Correct 193 ms 24036 KB Output is correct
28 Correct 174 ms 24012 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Incorrect 1 ms 352 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -