제출 #40851

#제출 시각아이디문제언어결과실행 시간메모리
40851grumpy_gordonPort Facility (JOI17_port_facility)C++14
0 / 100
22 ms23800 KiB
/* .:*+=%@@@@@@=-. .:=@#@@@#@@#######%==*. .-=####@######%*-.....:%##%. .*@###########%+:--........-%@- .*@##############@+--.........-:%- .+##################@==%%%%=+*:----+. .-@####################%++%@@@@@=+**%@@* .%###################@%%@@@###@%+:--%@@%. -@###################@%%%%*::*%++:-----=@+. -#####################@%=++++++*:-------.-=: .+####################@%++*::-:::--::*:::***=: .@#####################%=++*::::-:::++*=##@@#@- ..#####################@%%=++**:::::**+%@#@%%##-.. .%####################@@%=+++*+****::*=@######@. .=######################@%%==+==++**+=@%@##@###+:... -#######################@@@%%%===++=@@@%=++===*::--... -########################@@@@@@@%==%%=++==@@:::::*:--. ..:#########################@@@@@@%%======++++::-..:-.--... %#############################@###@%%@@%==%=%*----.--.::---. #############################################*-:*:-:---*---- . #############################################*--*--:---*---:-. #############################################+--::--::-*::-::. ###########################################+:*-.---.---.:---*-.. ###########################################**:-----------------. ##########################################@::**:--::::::--:::::- ###########################################:--:*:::::::::**::*+* ###########################################=:::***::::::**:::*+* ############################@@@@@@#########@+****::::********+++ ############################@%%%%%@@@@@@@###%+***::::::::***+==+ ############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+ #############################@%%%%%%%%%%@#####=::--------:*=%@%+ %###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%= ---------------------------------------------- -------------------------------------------- ---------------------------------------------- -------------------------------------------- ---------------------------------------------- o###########oo o##" ""##o o#" "## o#" "#o #" ## ## "## #" ## # ################### # # # # # # # # # # # # # #o # "#o ## "#o ## "#o o#" "#o ## "#o o#" "#ooo ooo#######oo ############### "######o o###"" "###o # ### o###o oooo ### oo####" o###**# #**# ############" ""##""""""""""########### # # oooooooo#"#** ## # # # # # ** ## # #o# #o# *****###ooo# ## ## o###o ## o##***## o########## #***#**##o o##" ""### #***##***# o#######o ### oo#### ##**####*# o##" ""#############"" ##****### ##" ## ##*##*### ## ### ##### ## ## ### # ## # ## ## # ## ## ## ### ## ###oo ### ""### ### ### */ #include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") //#pragma GCC target("avx,tune=native") //float __attribute__((aligned(32))) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; int mysqrt(ll x){ int l = 0, r = 1e9 + 1; while (r - l > 1){ int m = (l + r) / 2; if (m * (ll)m <= x) l = m; else r = m; } return l; } mt19937 rnd(1337); ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993; ll myrand(){ ll ZR = (XR * AR + YR * BR + CR) % MODR; XR = YR; YR = ZR; return ZR; } const int Mod = 1e9 + 7; int bpow(int x, int y){ if (y == 0) return 1; if (y == 1) return x; int ret = bpow(x, y >> 1); ret = (ret * (ll)ret) % Mod; if (y & 1) ret = (ret * (ll)x) % Mod; return ret; } int bdiv(int x, int y){ return (x * (ll)bpow(y, Mod - 2)) % Mod; } void setmin(int &x, int y){ x = min(x, y); } void setmax(int &x, int y){ x = max(x, y); } void setmin(ll &x, ll y){ x = min(x, y); } void setmax(ll &x, ll y){ x = max(x, y); } int gcd(int a, int b){ return a ? gcd(b % a, a) : b; } const ll llinf = 2e18 + 100; const int maxn = 2e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17; pair<int, int> a[maxw]; int arr[2 * maxw]; int n; vector<pair<int, int> > w; int p[maxw]; int r[maxw]; int get(int x){ return x == p[x] ? x : p[x] = get(p[x]); } void uni(int x, int y){ x = get(x); y = get(y); if (x == y) return; if (r[x] < r[y]) swap(x, y); p[y] = x; if (r[x] == r[y]) r[x]++; } bool used[maxw]; vector<int> e[maxw]; int col[maxw]; bool dfs(int v, int cs = 0){ col[v] = cs; used[v] = 1; for (auto i : e[v]) if (!used[i]){ if (dfs(i, cs ^ 1)) return 1; } else if (col[i] != (cs ^ 1)) return 1; return 0; } int main() { #ifdef ONPC //ifstream cin("a.in"); //ofstream cout("a.out"); freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #else //ifstream cin("sprinklers.in"); //ofstream cout("sprinklers.out"); //freopen("road.in", "r", stdin); //freopen("road.out", "w", stdout); #endif // ONPC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i++){ cin >> a[i].first >> a[i].second; a[i].first--; a[i].second--; arr[a[i].first] = i; arr[a[i].second] = -1; } for (int i = 0; i < n; i++) p[i] = i; /* for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i].first < a[j].first && a[i].second > a[j].first && a[i].second < a[j].second) uni(i, j); */ stack<int> q; stack<int> g; for (int i = 0; i < 2 * n; i++){ if (arr[i] < 0){ q.pop(); int last = (q.empty() ? inf : a[q.top()].second); vector<int> vsp; while (!g.empty() && a[g.top()].second < last) vsp.push_back(g.top()), g.pop(); reverse(vsp.begin(), vsp.end()); for (auto j : vsp) q.push(j); continue; } int id = arr[i]; if (!g.empty() && a[id].second > a[g.top()].second){ cout << 0; return 0; } int last = -1; stack<int> vsp; while (!q.empty() && a[q.top()].second < a[id].second){ if (last != -1){ if (get(last) == get(q.top())) break; uni(last, q.top()); } else last = q.top(); vsp.push(q.top()); q.pop(); } if (last != -1) w.push_back(make_pair(last, id)), g.push(id); else q.push(id); while (!vsp.empty()) q.push(vsp.top()), vsp.pop(); } for (auto it : w) if (get(it.first) == get(it.second)){ cout << 0; return 0; } for (auto it : w) e[it.first].push_back(it.second), e[it.second].push_back(it.first); int ans = 1; for (int i = 0; i < n; i++) if (!used[get(i)]) if (dfs(get(i))){ cout << 0; return 0; } else ans = (ans * 2) % mod; cout << ans; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:295:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
     if (!used[get(i)])
        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...