oj.uz

답안 #351143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351143 2021-01-19T12:59:47 Z teehandsome 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 1000 ms 14188 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;

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++) {
        for(int j=0;j<n;j++) {
            for(int k=0;k<n;k++) {
                if(adj[i][j]==adj[j][k] and adj[i][j]!=adj[i][k]) return 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);
            }
            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);
	}
	build(adj);
	return 1;
}

Compilation message

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

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 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 20 ms 1260 KB Output is correct
7 Execution timed out 1100 ms 14188 KB Time limit exceeded

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 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 20 ms 1260 KB Output is correct
7 Execution timed out 1100 ms 14188 KB Time limit exceeded

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 1 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 206 ms 6316 KB Output is correct
5 Execution timed out 1099 ms 14188 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 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 20 ms 1260 KB Output is correct
7 Execution timed out 1100 ms 14188 KB Time limit exceeded

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 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 20 ms 1260 KB Output is correct
7 Execution timed out 1100 ms 14188 KB Time limit exceeded