oj.uz

Submission #351152

# Submission time Handle Problem Language Result Execution time Memory
351152 2021-01-19T13:08:03 Z teehandsome Connecting Supertrees (IOI20_supertrees) C++14
21 / 100
 328 ms 30316 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

const int mxn=1e3+10;
vector<int> par;
vector<int> mxpath;
vector<int> group[mxn];
vector<vector<int>> adj;
vector<int> f[mxn];

int findp(int x) {
    while(par[x]!=x) { par[x]=par[par[x]]; x=par[x];}
    return x;
}
void unionset(int u,int v) {
    int U=findp(u); int V=findp(v);
    par[U]=V;
}
void solve(int idx) {
    if(group[idx].empty()) return;
    int len=group[idx].size();
    if(mxpath[group[idx][0]]==0) {
        return;
    }
    else if(mxpath[group[idx][0]]==2) {
        for(int i=0;i<len;i++) {
            int u=group[idx][i];
            int v=group[idx][(i+1)%len];
            adj[u][v]=adj[v][u]=1;
        }
    }
    else {
        for(int i=0;i<len-1;i++) {
            int u=group[idx][i];
            int v=group[idx][i+1];
            adj[u][v]=adj[v][u]=1;
        }

    }
}

int construct(std::vector<std::vector<int>> p) {
	int n=p.size(); par.resize(n); mxpath.resize(n);
	adj.resize(n,vector<int>(n,0));

	for(int i=0;i<n;i++) par[i]=i;
	for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(p[i][j]==3) return 0;
            if(p[i][j]>0) {
                int I=findp(i); int J=findp(j);
                unionset(i,j);
                f[i].push_back(j); f[j].push_back(i);
            }
            mxpath[i]=max(mxpath[i],p[i][j]);
            mxpath[j]=max(mxpath[j],p[i][j]);
        }
	}
	for(int i=0;i<n;i++) {
        par[i]=findp(par[i]);
        group[par[i]].push_back(i);
	}
	for(int i=0;i<n;i++) {
        solve(i);
	}
	for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(!p[i][j] and par[i]==par[j]) return 0;
        }
	}
	build(adj);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:78:21: warning: unused variable 'I' [-Wunused-variable]
   78 |                 int I=findp(i); int J=findp(j);
      |                     ^
supertrees.cpp:78:37: warning: unused variable 'J' [-Wunused-variable]
   78 |                 int I=findp(i); int J=findp(j);
      |                                     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 1644 KB Output is correct
7 Correct 312 ms 30208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 1644 KB Output is correct
7 Correct 312 ms 30208 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 255 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 8 ms 1132 KB Output is correct
17 Correct 145 ms 19968 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 6508 KB Output is correct
21 Correct 265 ms 25196 KB Output is correct
22 Correct 267 ms 24300 KB Output is correct
23 Correct 303 ms 28304 KB Output is correct
24 Correct 258 ms 24428 KB Output is correct
25 Correct 117 ms 15212 KB Output is correct
26 Correct 111 ms 14188 KB Output is correct
27 Correct 291 ms 30316 KB Output is correct
28 Correct 274 ms 24192 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 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 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 66 ms 6124 KB Output is correct
5 Correct 264 ms 23276 KB Output is correct
6 Correct 258 ms 22252 KB Output is correct
7 Correct 290 ms 26348 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 67 ms 5996 KB Output is correct
10 Correct 286 ms 23232 KB Output is correct
11 Correct 256 ms 22380 KB Output is correct
12 Correct 328 ms 28396 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Incorrect 1 ms 364 KB Too many ways to get from 0 to 4, should be 1 found no less than 2
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 1644 KB Output is correct
7 Correct 312 ms 30208 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 255 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 8 ms 1132 KB Output is correct
17 Correct 145 ms 19968 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 6508 KB Output is correct
21 Correct 265 ms 25196 KB Output is correct
22 Correct 267 ms 24300 KB Output is correct
23 Correct 303 ms 28304 KB Output is correct
24 Correct 258 ms 24428 KB Output is correct
25 Correct 117 ms 15212 KB Output is correct
26 Correct 111 ms 14188 KB Output is correct
27 Correct 291 ms 30316 KB Output is correct
28 Correct 274 ms 24192 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 1644 KB Output is correct
7 Correct 312 ms 30208 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 255 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 8 ms 1132 KB Output is correct
17 Correct 145 ms 19968 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 6508 KB Output is correct
21 Correct 265 ms 25196 KB Output is correct
22 Correct 267 ms 24300 KB Output is correct
23 Correct 303 ms 28304 KB Output is correct
24 Correct 258 ms 24428 KB Output is correct
25 Correct 117 ms 15212 KB Output is correct
26 Correct 111 ms 14188 KB Output is correct
27 Correct 291 ms 30316 KB Output is correct
28 Correct 274 ms 24192 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Incorrect 1 ms 364 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -