제출 #303260

#제출 시각아이디문제언어결과실행 시간메모리
303260Utaha슈퍼트리 잇기 (IOI20_supertrees)C++14
0 / 100
1 ms256 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; // typedef long double ld; #define F first #define S second #define ALL(a) a.begin(),a.end() #define SZ(a) ((int)a.size()) #define REP(i,n) for(int i=0;i<(n);i++) #define MP make_pair #define pb push_back #define eb emplace_back const int maxn = 1005; const int INF = 0x3f3f3f3f; const ll INF64 = 1e18; const ll MOD = ll(1e9+7); int n; vector<int> cmp; bool vis[maxn]; std::vector<std::vector<int>> ans; std::vector<std::vector<int>> p; void dfs(int u){ vis[u]=1; cmp.pb(u); REP(v,n) if(v!=u&&p[u][v]&&!vis[v]){ dfs(v); } } vector<int> _; bool vis2[maxn]; void dfs2(int u){ vis2[u]=1; _.pb(u); REP(v,n) if(v!=u&&p[u][v]==1&&!vis2[v]){ dfs2(v); } } void add(int x,int y){ ans[x][y]=ans[y][x]=1; } bool process(){ cout<<"process: "; for(int i:cmp){ cout<<i<<' '; } cout<<'\n'; for(int i:cmp) vis2[i] = 0; vector<int> ring; for(int i:cmp) if(!vis2[i]){ _.clear(); dfs2(i); for(int j:_){ cout<<j<<' '; } cout<<endl; for(int x:_) for(int y:_){ if(p[x][y]!=1) return 0; } REP(i,SZ(_)-1){ add(_[i],_[i+1]); } ring.pb(_[0]); } if(SZ(ring)==2){ return 0; } if(SZ(ring)>2){ ring.pb(ring[0]); REP(i,SZ(ring)-1){ add(ring[i],ring[i+1]); } } return 1; } int construct(std::vector<std::vector<int>> A) { p=A; n = p.size(); for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); ans.push_back(row); } REP(i,n) REP(j,n) if(p[i][j]==3) return 0; bool flag = 1; REP(i,n) if(!vis[i]){ cmp.clear(); dfs(i); flag &= process(); if(!flag) return 0; } build(ans); return 1; }
#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...