제출 #343093

#제출 시각아이디문제언어결과실행 시간메모리
343093bigDuck슈퍼트리 잇기 (IOI20_supertrees)C++14
46 / 100
278 ms26220 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount vector<pii> c1; vector<pii> c2; vector<int> c3; vector<vector<int> > P; int N; int r[1010][4]; vector<vector<int>> B; void b1(){ for(int i=0; i<N; i++){ if(r[i][1]==(-1)){ r[i][1]=i; int mx=i; for(int j=0; j<N; j++){ if( (P[i][j]==1) && (i!=j) ){ B[mx][j]=1; B[j][mx]=1; r[j][1]=i; mx=max(j, mx); } } c1.pb({i, mx}); } } } void b2(){ for(pii p1:c1){ int u1=p1.ft, v1=p1.sc; if(r[u1][2]==(-1)){ c2.pb({u1, u1}); int mx=u1; for(pii p2:c1){ int u2=p2.ft, v2=p2.sc; if(u2==u1){continue;} if( (r[u2][2]==(-1)) && (P[u1][u2]==2) ){ B[mx][u2]=1; B[u2][mx]=1; r[u1][2]=u1; r[u2][2]=u1; mx=u2; c2.back()={v1, v2}; } } if( (c2[c2.size()-1])==mp(u1, u1) ){ c2.pop_back(); } else{ B[u1][mx]=1; B[mx][u1]=1; } } } } bool check(){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ if(P[i][j]==3){ return false; } if( (r[i][1]==r[j][1]) && (P[i][j]!=1) ){ return false; } if( (r[i][2]==r[j][2]) && (r[i][2]!=(-1)) && (r[i][1]!=r[j][1]) && (P[i][j]!=2) ){ return false; } } } return true; } int construct(std::vector<std::vector<int>> p) { P=p; N=P.size(); memset(r, -1, sizeof(r)); B.resize(N); for(int i=0; i<N; i++){ B[i].resize(N); for(int j=0; j<N; j++){ B[i][j]=0; } } b1(); b2(); if(check()){ build(B); return 1; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...