Submission #204132

#TimeUsernameProblemLanguageResultExecution timeMemory
204132cheetoseMeetings (JOI19_meetings)C++17
0 / 100
3087 ms4592 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define X first #define Y second #define y0 y12 #define y1 y22 #define INF 987654321 #define PI 3.141592653589793238462643383279502884 #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c)) #define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c)) #define MEM0(a) memset((a),0,sizeof(a)); #define MEM_1(a) memset((a),-1,sizeof(a)); #define ALL(a) a.begin(),a.end() #define SYNC ios_base::sync_with_stdio(false);cin.tie(0) using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int, int> Pi; typedef pair<ll, ll> Pll; typedef pair<ld, ld> Pd; typedef vector<int> Vi; typedef vector<ll> Vll; typedef vector<ld> Vd; typedef vector<Pi> VPi; typedef vector<Pll> VPll; typedef vector<Pd> VPd; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tuple<ll, ll, ll> LLL; typedef vector<iii> Viii; typedef vector<LLL> VLLL; typedef complex<double> base; const int MOD = 1000000007; ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); } int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 }; int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 }; #include "meetings.h" #define kill kool Vi v[2005]; int num[2005][2005]; void discon(int x, int y) { int i=num[x][y]; int z=v[x].back(); int j=num[x][z]; swap(v[x][i],v[x][j]); num[x][z]=i; num[x][y]=-1; v[x].pop_back(); i=num[y][x]; z=v[y].back(); j=num[y][z]; swap(v[y][i],v[y][j]); num[y][z]=i; num[y][x]=-1; v[y].pop_back(); } void con(int x, int y) { v[x].pb(y); num[x][y]=(int)v[x].size()-1; v[y].pb(x); num[y][x]=(int)v[y].size()-1; } bool chk[2005], kill[2005]; int sz[2005]; int getSz(int N, int pp) { sz[N] = 1; for (int next : v[N]) { if (next == pp || kill[next])continue; sz[N] += getSz(next, N); } return sz[N]; } int get_centroid(int N, int pp, int cap) { for (int next : v[N]) { if (kill[next] || next == pp)continue; if (sz[next]>cap) return get_centroid(next, N, cap); } return N; } void Solve(int N) { chk[0] = chk[1] = chk[2] = 1; int w = Query(0, 1, 2); if (w>2) { chk[w] = 1; con(0, w); con(1, w); con(2, w); } else { fup(i, 0, 2, 1)if (w != i)con(i, w); } fup(i, 3, N - 1, 1) { if (chk[i])continue; chk[i] = 1; MEM0(kill); int pr = 0; while (1) { int cap = getSz(pr, -1); int R = get_centroid(pr, -1, cap / 2); kill[R] = 1; int t=-1; fup(j, 1, (int)v[R].size() - 1, 2) { int a = v[R][j - 1], b = v[R][j]; int x = Query(a, i, b); if (x == i) { int T = Query(R, i, a); if (T == i) { discon(R, a); con(R, i); con(i, a); } else { discon(R, b); con(R, i); con(i, b); } goto FIN; } else if(x!=R)t=-1; } if (v[R].size() & 1) { int x = Query(R, i, v[R].back()); if (x == i) { int B = v[R].back(); discon(R, B); con(R, i); con(i, B); goto FIN; } else if(x!=R)t=x; } if (t == -1) { con(R, i); goto FIN; } else { pr = t; } } FIN:; } fup(i, 0, N - 1, 1) { for (int x : v[i]) { if (x>i)Bridge(i,x); } } }/* int main() { }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...