제출 #301973

#제출 시각아이디문제언어결과실행 시간메모리
301973Trickster슈퍼트리 잇기 (IOI20_supertrees)C++14
21 / 100
280 ms30328 KiB
#include "supertrees.h" #include <algorithm> #include <string.h> #include <iostream> #include <stdio.h> #include <vector> #include <queue> #include <cmath> #include <set> #include <map> using namespace std; #define N 1010 #define ff first #define ss second #define ll long long #define pb push_back #define mod 1000000007 #define pii pair <int, int> #define sz(a) int(a.size()) #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;} int P[N]; int n, ans; int arr[N][N]; int pat[N][N]; vector <int> E; int vis[N], vis2[N]; int ata(int x) { if(x == P[x]) return x; return P[x] = ata(P[x]); } void uni(int a, int b) { a = ata(a); b = ata(b); if(a == b) return; P[b] = a; arr[a][b] = arr[b][a] = 1; } void dfs(int nd) { E.pb(nd); vis[nd] = 1; for(int i = 0; i < n; i++) if(i != nd) { if(pat[nd][i] == 1) vis2[i] = (vis2[i] == 1 ? 2 : vis2[i]); if(pat[nd][i] == 0) vis2[i] = 0; } for(int i = 0; i < n; i++) if(pat[nd][i] == 2 && !vis[i]) { if(vis2[i] != 1) { if(vis2[i] == 2) continue; // ans = 1; return; } dfs(i); return; } } void upd(int nd) { vis[nd] = 1; for(int i = 0; i < n; i++) { if(ata(i) == ata(nd)) continue; if(pat[nd][i] == 1) { if(vis[i] == 1) { // ans = 1; return; } uni(nd, i); } } } int construct(vector<vector<int>> p) { n = p.size(); for(int i = 0; i < n; i++) P[i] = i; for(int i = 0; i < n; i++) for(int h = 0; h < n; h++) { pat[i][h] = p[i][h]; if(p[i][h] == 3) return 0; } for(int i = 0; i < n; i++) { if(vis[i]) continue; E.clear(); memset(vis2, 0, sizeof(vis2)); for(int h = 0; h < n; h++) { if(i == h) continue; if(p[i][h] == 1) vis2[h] = 2; if(p[i][h] == 2) vis2[h] = 1; } dfs(i); if(E.size() == 2) return 0; int last = -1; for(auto h: E) { if(last != -1) arr[last][h] = arr[h][last] = 1; upd(h); last = h; } if(E.size() == 1) continue; arr[E[0]][last] = arr[last][E[0]] = 1; } if(ans == 1) return 0; for(int i = 0; i < n; i++) for(int h = 0; h < n; h++) if(!p[i][h] && ata(i) == ata(h)) return 0; vector <vector <int>> ret; ret.resize(n); for(int i = 0; i < n; i++) for(int h = 0; h < n; h++) ret[i].pb(arr[i][h]); build(ret); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
supertrees.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      |
#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...