oj.uz

답안 #351153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351153 2021-01-19T13:09:20 Z teehandsome 슈퍼트리 잇기 (IOI20_supertrees) C++14
21 / 100
 305 ms 30188 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;
            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

# 결과 실행 시간 메모리 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 13 ms 1644 KB Output is correct
7 Correct 295 ms 30188 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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 13 ms 1644 KB Output is correct
7 Correct 295 ms 30188 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 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 1260 KB Output is correct
13 Correct 262 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1280 KB Output is correct
17 Correct 165 ms 18028 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 5996 KB Output is correct
21 Correct 262 ms 23276 KB Output is correct
22 Correct 255 ms 22252 KB Output is correct
23 Correct 305 ms 26220 KB Output is correct
24 Correct 256 ms 22252 KB Output is correct
25 Correct 117 ms 13292 KB Output is correct
26 Correct 109 ms 12328 KB Output is correct
27 Correct 287 ms 28368 KB Output is correct
28 Correct 275 ms 22200 KB Output is correct

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 0 ms 364 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 68 ms 6124 KB Output is correct
5 Correct 267 ms 23216 KB Output is correct
6 Correct 254 ms 22252 KB Output is correct
7 Correct 284 ms 26348 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 65 ms 6012 KB Output is correct
10 Correct 264 ms 23340 KB Output is correct
11 Correct 259 ms 22288 KB Output is correct
12 Correct 284 ms 28524 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

# 결과 실행 시간 메모리 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 13 ms 1644 KB Output is correct
7 Correct 295 ms 30188 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 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 1260 KB Output is correct
13 Correct 262 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1280 KB Output is correct
17 Correct 165 ms 18028 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 5996 KB Output is correct
21 Correct 262 ms 23276 KB Output is correct
22 Correct 255 ms 22252 KB Output is correct
23 Correct 305 ms 26220 KB Output is correct
24 Correct 256 ms 22252 KB Output is correct
25 Correct 117 ms 13292 KB Output is correct
26 Correct 109 ms 12328 KB Output is correct
27 Correct 287 ms 28368 KB Output is correct
28 Correct 275 ms 22200 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Incorrect 0 ms 364 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 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 13 ms 1644 KB Output is correct
7 Correct 295 ms 30188 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 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 1260 KB Output is correct
13 Correct 262 ms 22252 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1280 KB Output is correct
17 Correct 165 ms 18028 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 66 ms 5996 KB Output is correct
21 Correct 262 ms 23276 KB Output is correct
22 Correct 255 ms 22252 KB Output is correct
23 Correct 305 ms 26220 KB Output is correct
24 Correct 256 ms 22252 KB Output is correct
25 Correct 117 ms 13292 KB Output is correct
26 Correct 109 ms 12328 KB Output is correct
27 Correct 287 ms 28368 KB Output is correct
28 Correct 275 ms 22200 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Incorrect 0 ms 364 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -