제출 #623046

#제출 시각아이디문제언어결과실행 시간메모리
623046radalMeetings (JOI19_meetings)C++17
29 / 100
1998 ms96256 KiB
#include <bits/stdc++.h> #include "meetings.h" #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr int N = 2e3+10,mod = 998244353,inf = 1e9+10,sq = 700; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k /= 2; } return z; } int noob; vector<int> tmp[N][N]; bool cmp(int u,int v){ int x = Query(u,v,noob); if (x == u) return 1; return 0; } void dojob(vector<int> ve,int dep = 0){ int n = ve.size(); if (n == 1) return; if (n == 2){ if (ve[1] < ve[0]) swap(ve[0],ve[1]); Bridge(ve[0],ve[1]); return; } int u = ve[0],v = ve[1]; vector<int> path; tmp[u][dep].pb(u); tmp[v][dep].pb(v); rep(i,2,n){ int w = ve[i]; int x = Query(u,v,w); if (x == w) path.pb(w); tmp[x][dep].pb(w); } for (int w : ve) if (!tmp[w][dep].empty()){ dojob(tmp[w][dep],dep+1); tmp[w][dep].clear(); } if (path.empty()){ Bridge(u,v); return; } noob = u; sort(all(path),cmp); int sz = path.size(); Bridge(u,path[0]); Bridge(v,path.back()); rep(i,1,sz){ int x = path[i],y = path[i-1]; if (x > y) swap(x,y); Bridge(x,y); } } void Solve(int n){ vector<int> ve; rep(i,0,n) ve.pb(i); dojob(ve); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...