Some problems don't have a tutorial yet, those should be added later.
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000;
int dpfr[2][N + 1], dp[N + 1], n, gr[N + 1];
vector<int> tr[N + 1];
vector<int> cn;
int getcn(int v = 1, int p = 0){
bool ok = true;
int s = 1;
f(i, 0, tr[v].size()){
int u = tr[v][i];
if (u == p)continue;
int t = getcn(u, v);
if (t > n >> 1)ok = false;
s += t;
}
if (n - s > n >> 1)ok = false;
if (ok)cn.push_back(v);
return s;
}
int G;
void pl(int v, int p = 0){
dp[v] = dp[p] + 1;
gr[v] = G;
f(i, 0, tr[v].size()){
int u = tr[v][i];
if (u == p)continue;
pl(u, v);
}
}
ll P(int x) { return (ll)x * (x - 1) >> 1; }
void solve(){
scanf("%d", &n);
f(i, 1, n + 1)tr[i].clear();
f(j, 0, 2)f(i, 1, n + 1)dpfr[j][i] = 0;
f(i, 2, n + 1){
int t;
scanf("%d", &t);
tr[i].push_back(t);
tr[t].push_back(i);
}
cn.clear();
getcn();
ll an = P(n);
if ((int)cn.size() == 1){
pl(cn[0]);
f(i, 1, n + 1)++dpfr[0][dp[i]];
f(i, 1, n + 1)an += P(dpfr[0][i]);
}else {
G = 0;
dp[cn[1]] = 0;
pl(cn[0], cn[1]);
G = 1;
dp[cn[0]] = 0;
pl(cn[1], cn[0]);
dp[cn[0]] = 1;
f(i, 1, n + 1)++dpfr[gr[i]][dp[i]];
f(i, 1, n + 1){
an += P(dpfr[0][i]);
an += P(dpfr[1][i]);
an -= (ll)dpfr[0][i] * dpfr[1][i];
}
}
printf("%lld\n", an);
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000, md = 1e9 + 7;
int x[N], y[N], fc[N + 1], xt[N + 1], yt[N + 1];
void solve(){
int n;
scanf("%d", &n);
n <<= 1;
f(i, 0, n)scanf("%d%d", x + i, y + i);
f(i, 0, n)xt[i] = x[i];
sort(xt, xt + n);
f(i, 0, n)yt[i] = y[i];
sort(yt, yt + n);
n >>= 1;
if (xt[n - 1] == xt[n]) { printf("0\n"); return; }
if (yt[n - 1] == yt[n]) { printf("0\n"); return; }
n <<= 1;
int a = 0, b = 0;
f(i, 0, n)if (x[i] < xt[n >> 1])y[i] < yt[n >> 1] ? ++a : ++b;
int an = (ll)fc[a] * fc[b] % md;
printf("%d\n", an);
}
int main(){
fc[0] = 1;
f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000, md = 1e9 + 7;
int fc[N + 1], inv[N + 1], fcin[N + 1];
void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
void sb(int &x, int y) { if ((x -= y) < 0)x += md; }
int ch(int n, int r) { return (ll)fc[n] * fcin[r] % md * fcin[n - r] % md; }
void solve(){
int n;
scanf("%d", &n);
int s = 0, an = 0;
f(i, 0, n){
ad(s, ch(n, i + 1));
int t;
scanf("%d", &t);
ad(an, (ll)t * s % md);
sb(s, ch(n, i));
}
printf("%d\n", an);
}
int main(){
fc[0] = 1;
f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
inv[1] = 1;
f(i, 2, N + 1)inv[i] = md - md / i * (ll)inv[md % i] % md;
fcin[0] = 1;
f(i, 1, N + 1)fcin[i] = (ll)fcin[i - 1] * inv[i] % md;
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define all(c) (c).begin(),(c).end()
int T,n,k;
multiset<int> A,B;
int main(){
cin>>T;
while(T--){
A.clear();
B.clear();
cin>>n>>k;
for(int x,i=0; i<n; ++i){
scanf("%d",&x);
A.insert(x);
}
for(int x,i=0; i<n; ++i){
scanf("%d",&x);
if(A.find(x)!=A.end())
A.erase(A.find(x));
else
B.insert(x);
}
if(A.empty())
puts("YES");
else if(A.size()==1 && B.size()==1 && abs(*A.begin()-*B.begin())<=k)
puts("YES");
else
puts("NO");
}
return 0;
}
Tutorial is loading...
Short and precise explanation by TooDumbToWin can be found here.
Code1
//#pragma comment(linker, "/STACK:16777216")
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, res;
vector<vector<int> > g, o, v;
vector<vector<vector<int> > > cyc;
set<pair<int, int> > br;
int low[N], idx[N], dfs;
bool vis[N];
void DFS(int u, int p) {
low[u] = idx[u] = ++dfs;
for (auto v : g[u])
if (!idx[v]) {
DFS(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > idx[u])
br.insert({ min(u,v),max(u,v) });
}
else if (v != p)
low[u] = min(low[u], idx[v]);
}
void DFS(int u) {
if (vis[u])
return;
v.back().push_back(u);
vis[u] = true;
for (auto &w : g[u])
DFS(w);
}
vector<vector<int> > options;
void findOptions(int u, int p) {
if (g[u].size() > 3 && vis[u]) {
if (options.back()[0] == options.back().back())
options.back().pop_back();
return;
}
if (p != -1 && g[u].size() == 3)
return;
vis[u] = true;
for (auto v : g[u])
if (v != p) {
if (p == -1) {
if (vis[v])
continue;
options.push_back(vector<int>());
options.back().push_back(u);
}
options.back().push_back(v);
findOptions(v, u);
}
}
void findCycles(vector<int> &comp, vector<vector<int> > &cyc) {
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (auto u : comp) {
if (vis[u])
continue;
cyc.push_back(vector<int>());
queue<int> q;
q.push(u);
vis[u] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cyc.back().push_back(u);
for (auto v : g[u])
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (cyc.back().size() == 1)
cyc.pop_back();
}
if (cyc.size() == 1) {
int at = -1;
for (auto x : cyc[0])
if (g[x].size() == 4) {
at = x;
break;
}
if (at != -1) {
for (int i = 0; i < n; ++i)
vis[i] = 0;
options.clear();
findOptions(at, -1);
assert(options.size() == 2);
cyc = options;
}
}
assert(cyc.size() <= 2);
}
int findClosest(const vector<int> &v, int x) {
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
int cur = 1e9;
if (idx != v.size())
cur = v[idx] - x;
if (idx != 0)
cur = min(cur, x - v[idx - 1]);
return cur;
}
int calc(int u, int p) {
int ret = findClosest(cyc[0][0], u);
for (auto v : g[u])
if (v != p && br.find({ min(u,v),max(u,v) }) != br.end())
ret = min(ret, calc(v, u));
res = min(res, ret + findClosest(v[1], u));
return ret;
}
int main()
{
int t;
scanf("%d", &t);
int totalN=0;
while (t--) {
scanf("%d", &n);
totalN+=n;
g.clear();
g.resize(n);
if (n < 1 || n>100000) {
puts("invalid n");
exit(1);
}
set<pair<int, int> > e;
for (int i = 1, a, b; i < n; ++i) {
scanf("%d%d", &a, &b);
if (a<1 || a>n || b<1 || b>n) {
puts("Invalid (a, b)");
exit(2);
}
if (a > b)
swap(a, b);
if (e.insert({ a,b }).second == false) {
puts("Multiple edges");
exit(3);
}
--a; --b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (int i = 0; i < n; ++i)
idx[i] = 0;
dfs = 0;
v.clear();
cyc.clear();
for (int i = 0; i < n; ++i)
if (!vis[i]) {
v.push_back(vector<int>());
if (v.size() == 4)
break;
DFS(i);
}
if (v.size() == 4) {
puts("-1");
continue;
}
if (v.size() == 1) {
puts("0");
continue;
}
br.clear();
for (int i = 0; i < n; ++i)
if (!idx[i])
DFS(i, -1);
o = g;
for (int i = 0; i < n; ++i)
for (int j = 0; j < g[i].size(); ++j)
if (br.find({ min(i,g[i][j]),max(i,g[i][j]) }) != br.end()) {
g[i][j] = g[i].back();
g[i].pop_back();
--j;
}
cyc.resize(v.size());
for (int i = 0; i < v.size(); ++i)
findCycles(v[i], cyc[i]);
for (auto &cycles : cyc)
for (auto &x : cycles) {
sort(x.begin(), x.end());
assert(x.size() >= 3);
}
res = 1e9;
if (v.size() == 2) {
if (cyc[0].empty()) {
v[0].swap(v[1]);
cyc[0].swap(cyc[1]);
}
sort(v[1].begin(), v[1].end());
g = o;
for (auto x : cyc[0][0])
calc(x, -1);
printf("%d\n", res);
continue;
}
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
if (cyc[j].size() < cyc[j + 1].size()) {
v[j].swap(v[j + 1]);
cyc[j].swap(cyc[j + 1]);
}
if (cyc[0].size() == 2) {
pair<int, int> A(1e9, 1e9), B(1e9, 1e9);
for (int it = 1; it <= 2; ++it) {
for (int i = 0; i < v[it].size(); ++i) {
A.first = min(A.first, findClosest(cyc[0][0], v[it][i]));
A.second = min(A.second, findClosest(cyc[0][1], v[it][i]));
}
swap(A, B);
}
res = min(A.first + B.second, A.second + B.first);
printf("%d\n", res);
continue;
}
if (!cyc[1].empty()) {
for (int i = 0; i < 2; ++i) {
int curA = 1e9;
for (auto x : v[2])
curA = min(curA, findClosest(cyc[i][0], x));
int curB = 1e9;
for (auto x : v[2])
curB = min(curB, findClosest(cyc[!i][0], x));
for (auto x : v[i])
curB = min(curB, findClosest(cyc[!i][0], x));
res = min(res, curA + curB);
}
printf("%d\n", res);
continue;
}
options.clear();
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (auto u : cyc[0][0])
if (g[u].size() > 2) {
findOptions(u, -1);
break;
}
assert(options.size() == 3);
for (auto &x : options)
sort(x.begin(), x.end());
int cur[2][3] = {};
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 3; ++j) {
cur[i][j] = 1e9;
for (auto x : v[i + 1])
cur[i][j] = min(cur[i][j], findClosest(options[j], x));
}
for (int i = 0; i < 3; ++i) {
res = min(res, cur[0][i] + min(cur[1][!i], cur[1][3 - i - !i]));
res = min(res, cur[1][i] + min(cur[0][!i], cur[0][3 - i - !i]));
}
printf("%d\n", res);
}
cerr<<totalN<<endl;
assert(totalN<=5000000);
return 0;
}
Code2
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
typedef vector<pair<int, int> > vp;
int const N = 100000, inf = 1e9;
vp g[N + 1];
vector<int> cy[N];
int vis[N + 1], vs = 1, n;
struct CM{
vector<set<int> > v;
set<int> all;
CM(){}
bool operator <(CM const &o)const { return v.size() > o.v.size(); }
bool in(int x) { return all.find(x) != all.end(); }
};
bool in(int x, set<int> const &st) { return st.find(x) != st.end(); }
int getCost(int x, set<int> const &st){
set<int>::iterator it = st.lower_bound(x);
int an = it == st.end() ? inf : *it - x;
if (it == st.begin())return an;
--it;
return min(an, x - *it);
}
int getCost(set<int> const &a, set<int> const &b){
int an = inf;
set<int>::iterator ita = a.begin(), itb = b.begin();
while (ita != a.end() && itb != b.end()){
an = min(an, abs(*ita - *itb));
if (*ita < *itb)++ita; else ++itb;
}
return an;
}
vector<CM> cm;
map<vector<int>, int> mp;
int getId(vector<int> const &v){
map<vector<int>, int>::iterator it = mp.find(v);
if (it == mp.end()){
int an = mp.size();
cm.back().v.push_back(set<int>());
return mp[v] = an;
}
return it->second;
}
int C;
vp build(int v, int p = 0){
vp c;
vis[v] = 0;
f(i, 0, g[v].size()){
int u = g[v][i].first;
if (u == p)continue;
if (vis[u] == 0)c.push_back(make_pair(C, u)), cy[g[v][i].second].push_back(C++);
else {
vp t = build(u, v);
while (t.size())c.push_back(t.back()), cy[g[v][i].second].push_back(t.back().first), t.pop_back();
}
}
f(i, 0, c.size())if (c[i].second == v)c.erase(c.begin() + i), --i;
vis[v] = 1;
return c;
}
void geted(int v){
vis[v] = 0;
cm.back().all.insert(v);
f(i, 0, g[v].size()){
int u = g[v][i].first;
int id = g[v][i].second;
if (!cy[id].empty()){
sort(cy[id].begin(), cy[id].end());
int cid = getId(cy[id]);
cm.back().v[cid].insert(v);
cm.back().v[cid].insert(u);
cy[id].clear();
}
if (vis[u] == 0)continue;
geted(u);
}
}
void visi(int v){
if (vis[v] == vs)return;
vis[v] = vs;
f(i, 0, g[v].size())visi(g[v][i].first);
}
int go(int v, int p, int mn = inf){
int an = mn + getCost(v, cm[0].v[0]);
mn = min(mn, getCost(v, cm[1].all));
f(i, 0, g[v].size()){
int u = g[v][i].first;
if (u == p)continue;
an = min(an, go(u, v, mn));
}
return an;
}
int solve(){
scanf("%d", &n);
f(i, 1, n + 1)g[i].clear();
f(i, 1, n)cy[i].clear();
f(i, 1, n){
int a, b;
scanf("%d%d", &a, &b);
g[a].push_back(make_pair(b, i));
g[b].push_back(make_pair(a, i));
}
int cmp = 0;
f(i, 1, n + 1)vis[i] = inf;
f(i, 1, n + 1)if (vis[i] > vs)++vs, visi(i), ++cmp;
if (cmp == 1)return 0;
if (cmp > 3)return -1;
cm.clear();
f(i, 1, n + 1)if (vis[i] > 1){
cm.push_back(CM());
mp.clear();
build(i);
geted(i);
}
sort(cm.begin(), cm.end());
int an = inf;
if (cmp == 2){
an = getCost(cm[0].v[0], cm[1].all);
f(i, 1, n + 1)if (in(i, cm[0].v[0]))f(j, 0, g[i].size())if (!in(g[i][j].first, cm[0].v[0]))an = min(an, go(g[i][j].first, i));
return an;
}
if (cm[0].v.size() > 1){
f(i, 0, cm[0].v.size())f(j, 0, cm[0].v.size())if (i != j)an = min(an, getCost(cm[0].v[i], cm[1].all) + getCost(cm[0].v[j], cm[2].all));
return an;
}
int a = getCost(cm[0].v[0], cm[1].all);
int b = getCost(cm[0].v[0], cm[2].all);
int c = getCost(cm[1].v[0], cm[0].all);
int d = getCost(cm[1].v[0], cm[2].all);
return min(b + min(c, d), d + min(a, b));
}
int main(){
int t;
scanf("%d", &t);
while (t--)printf("%d\n", solve());
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000;
double const eps = 1e-7;
int n, a, q;
long double an[N];
bool eq(double a, double b) { return abs(a - b) <= eps; }
struct V{
double x, y;
V(double a = 0.0, double b = 0.0):x(a), y(b) {}
void sc() { scanf("%lf%lf", &x, &y); }
double operator |(V const &o)const {
return x * o.y - o.x * y;
}
bool operator <(V const &o)const {
if (eq(x, o.x))return y < o.y;
return x < o.x;
}
V operator -(V const &o)const { return V(x - o.x, y - o.y); }
void pr() { printf("%lf %lf\n", x, y); }
}st[N];
pair<V, int> qu[N];
bool cmpr(V const &a, V const &b){
V v1 = a - st[0], v2 = b - st[0];
return (v1 | v2) < -eps;
}
vector<V> ch;
void getCh(){
sort(st + 1, st + n, cmpr);
ch.push_back(st[0]);
f(i, 1, n){
while ((int)ch.size() > 1 && (st[i] - ch.back() | ch.back() - ch[ch.size() - 2]) < eps)ch.pop_back();
ch.push_back(st[i]);
}
}
double getx(double xs, double z, double xq){
return xs + z / (z + a) * (xq - xs);
}
int left(int x) { return x ? x - 1 : ch.size() - 1; }
int right(int x) { return x + 1 == (int)ch.size() ? 0 : x + 1; }
void solve(){
scanf("%d%d", &n, &a);
f(i, 0, n)st[i].sc();
double mnz = st[0].y, mxz = st[0].y;
f(i, 1, n){
mnz = min(mnz, st[i].y);
mxz = max(mxz, st[i].y);
}
f(i, 0, n)st[i].y = a - st[i].y;
sort(st, st + n);
ch.clear();
getCh();
scanf("%d", &q);
f(i, 0, q){
qu[i].first.sc();
qu[i].second = i;
}
sort(qu, qu + q);
int lp = 0, rp = 0;
f(i, 0, ch.size())ch[i].y = a - ch[i].y;
while (ch[right(rp)].y < ch[rp].y)rp = right(rp);
while (ch[left(lp)].y > ch[lp].y)lp = left(lp);
f(i, 0, q){
while (true){
int ni = right(lp);
if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) < getx(ch[lp].x, ch[lp].y, qu[i].first.x))lp = ni;
else break;
}
while (true){
int ni = right(rp);
if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) > getx(ch[rp].x, ch[rp].y, qu[i].first.x))rp = ni;
else break;
}
double x = abs(getx(ch[rp].x, ch[rp].y, qu[i].first.x) - getx(ch[lp].x, ch[lp].y, qu[i].first.x));
double y = getx(0, mxz, qu[i].first.y) - getx(0, mnz, qu[i].first.y);
an[qu[i].second] = (long double) x * y;;
}
f(i, 0, q)printf("%.10lf\n", (double)an[i]);
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef long long ll;
const int N = 10010;
int n , q,T;
vector<pii> g[N];
vector<int> ad[N],rm[N];
ll w[N],ans = 0;
void dfs(int u , int p){
int id1 = -1 , id2 = -1;
for(auto v : g[u]){
if(v.first==p)continue;
w[v.first] = w[u] + v.second;
dfs(v.first,u);
if(id1 == -1)id1 = id2 = v.first;
if(rm[v.first].size()>rm[id1].size())id1 = v.first;
if(ad[v.first].size()>ad[id2].size())id2 = v.first;
}
if(id1 != -1)rm[u].swap(rm[id1]);
if(id2 != -1)ad[u].swap(ad[id2]);
for(auto v : g[u]){
if(v.first == p)continue;
for(auto k : ad[v.first])ad[u].push_back(k);
for(auto k : rm[v.first])rm[u].push_back(k);
ad[v.first].clear(),rm[v.first].clear();
}
while(ad[u].size() && rm[u].size()){
int f1 = ad[u].back(),f2 = rm[u].back();
ad[u].pop_back(),rm[u].pop_back();
ans += w[f1]+w[f2]-2*w[u];
}
}
int main(){
cin >> T;
while(T--){
cin >> n;
ans = 0;
for (int i = 1; i <= n; ++i)ad[i].clear(),rm[i].clear(),g[i].clear();
for (int u , v,w , i = 0 ; i < n-1 ; ++i){
scanf("%d%d%d",&u,&v,&w);
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
cin >> q;
for(int u , v , i = 0 ; i < q ; ++i){
scanf("%d%d",&u,&v);
ad[u].push_back(u);
rm[v].push_back(v);
}
dfs(1,-1);
cout << ans << endl;
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1001;
int n , l , dp[N][N],T;
pii a[N];
int calc(int idx , int time){
if(idx > n || time > l+1)return -N;
if(idx == n && time == l+1)return 0;
int &ret = dp[idx][time];
if(ret != -1)return ret;
ret = max(calc(idx,time+1),calc(idx+1,time));
if(time >= a[idx].first)
ret = max(ret,1+calc(idx+1,time+a[idx].second));
return ret;
}
int main(){
cin >> T;
while(T--){
memset(dp,-1,sizeof dp);
cin >> n >> l;
for (int i = 0; i < n; ++i)scanf("%d%d",&a[i].first,&a[i].second);
printf("%d\n",calc(0,1));
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n , m , r,T;
vector< vector<int> > g;
multiset< pii > hv[100002];
multiset<pii> cur;
int
ALL_PEOPLE = 0;
bool check(int md){
cur.clear();
for(int i = 0 ; i < m ; ++i)hv[i].clear();
for(int j = 0 ; j < md ; ++j)cur.insert(make_pair(-2,m));
for(int j = 0 ; j < n ; ++j){
for (int i = 0; i < m; ++i){
int rem = g[i][j];
vector<int> nw;
while(rem > 0){
assert(cur.size() == md);
if(hv[i].size()){
pii fr = *--hv[i].end();
hv[i].erase(--hv[i].end());
cur.erase(cur.find(fr));
cur.insert(make_pair(j,i));
nw.push_back(j);
}else{
pii em = *cur.begin();
if(em.first >= j-1)return false;
cur.erase(cur.begin());
if(em.second != m)
hv[em.second].erase(hv[em.second].find(em));
cur.insert(make_pair(j,i));
nw.push_back(j);
}
rem -= r;
}
for(int k = 0 ; k < nw.size();++k){
hv[i].insert(make_pair(nw[k],i));
}
}
}
return 1;
}
int main(){
// freopen("2.in","r",stdin);
// freopen("2.out","w",stdout);
cin >> T;
while(T--){
scanf("%d%d%d",&m,&n,&r);
g.clear();
g.resize(m);
int total = 0;
for (int i = 0; i < m; ++i){
g[i].resize(n);
for(int j = 0 ; j < n ; ++j){
scanf("%d",&g[i][j]);
total += g[i][j];
}
}
ALL_PEOPLE += total;
int lo = 1, hi = total,best = -1;
while(lo <= hi){
int md = (lo + hi)/2;
if(check(md)){
best = md;
hi = md-1;
}else{
lo=md+1;
}
}
cout << best << endl;
}
//cout << "ALL PEOPLE = " << ALL_PEOPLE << endl;
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define all(c) (c).begin(),(c).end()
int n,m,cmp[2*N],t;
vi g[2*N],rg[2*N];
bool vis[2*N];
int Not(int x){
return x>=n?x-n:x+n;
}
void addEdge(int a, int b){
g[Not(b)].pb(a);
g[Not(a)].pb(b);
rg[a].pb(Not(b));
rg[b].pb(Not(a));
}
stack<int> st;
void dfs(int u, vi g[N], int cc=-1){
vis[u]=1;
for(int i=0; i<g[u].size(); ++i)
if(!vis[g[u][i]])
dfs(g[u][i], g, cc);
if(cc==-1){
st.push(u);
}else{
cmp[u]=cc;
}
}
void get(int &x, int l, int r){
assert(scanf("%d",&x)==1);
assert(x>=l && x<=r);
}
int main(){
get(t,1,1000);
while(t--){
get(n, 1, 100000);
get(m, 0, 100000);
for(int a,b,c,i=0; i<m; ++i){
get(a,1,n);
get(b,1,n);
assert(a!=b);
get(c,0,1);
--a;--b;
if(c)
addEdge(Not(a), Not(b));
addEdge(a, b);
}
for(int i=0; i<2*n; ++i)
vis[i]=0;
for(int i=0; i<2*n; ++i)
if(!vis[i])
dfs(i,g);
for(int i=0; i<2*n; ++i)
vis[i]=0;
int cc=0;
while(!st.empty()){
int u=st.top();
st.pop();
if(vis[u])continue;
dfs(u, rg, cc++);
}
bool win=1;
for(int i=0; i<n && win; ++i){
if(cmp[i]==cmp[Not(i)])
win=0;
}
if(win)
puts("YES");
else
puts("NO");
for(int i=0; i<2*n; ++i){
g[i].clear();
rg[i].clear();
}
}
return 0;
}
