9.6万

rw-chen
I-AK-IOI
L._47
acwing_090

77777777777

mzx

modinte
Catch-22

fwyize
Dogel
Caesar123
Aigrl
ZXG_DXX

2020-02-14 12:41
#include <iostream>

using namespace std;

const int N = 10010;

int n,m,val;
int w[N],v[N];
int p[N],f[N];

int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
cin >> n >> m >> val;
for(int i = 1;i <= n;i ++)scanf("%d%d",&w[i],&v[i]),p[i] = i;
for(int i = 1;i <= m;i ++)
{
int a,b;
scanf("%d%d",&a,&b);
int pa = find(a),pb = find(b);
if(pa != pb)
{
w[pa] += w[pb];
v[pa] += v[pb];
p[pb] = pa;
}
}

for(int i = 1;i <= n;i ++)
if(i == find(i))
{
for(int j = val;j >= w[i];j --)
f[j] = max(f[j],f[j - w[i]] + v[i]);
}

cout << f[val];
}


2020-02-14 12:17
#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010;

int p[N],n,m;

int get(int x,int y)
{
return x * n + y;
}

int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}

int main()
{
cin >> n >> m;
for(int i = 0;i < n * n;i ++)p[i] = i;

for(int i = 1;i <= m;i ++)
{
int x,y;
char d;
cin >> x >> y >> d;
x --,y --;
int a = get(x,y),b;
if(d == 'D')
{
b = get(x + 1,y);
if(find(a) == find(b))
{
cout << i;
return 0;
}
else p[find(a)] = find(b);
}
else
{
b = get(x,y + 1);
if(find(a) == find(b))
{
cout << i;
return 0;
}
else p[find(a)] = find(b);
}
}

puts("draw");

return 0;
}


2020-02-13 16:37

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = 1000010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int q[N], d[N];
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
d[b] ++ ;
}

void topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n + m; i ++ )
if (!d[i])
q[ ++ tt] = i;

while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if ( -- d[j] == 0)
q[ ++ tt] = j;
}
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++ )
{
memset(st, 0, sizeof st);
int cnt;
scanf("%d", &cnt);
int start = n, end = 1;
while (cnt -- )
{
int stop;
scanf("%d", &stop);
start = min(start, stop);
end = max(end, stop);
st[stop] = true;
}

int ver = n + i;
for (int j = start; j <= end; j ++ )
}

topsort();

for (int i = 1; i <= n; i ++ ) dist[i] = 1;
for (int i = 0; i < n + m; i ++ )
{
int j = q[i];
for (int k = h[j]; ~k; k = ne[k])
dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);
}

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);

printf("%d\n", res);

return 0;
}


2020-02-13 15:27
#include <iostream>
#include <cstring>
#include <bitset>

using namespace std;

const int N = 30010,M = 30010;

int idx,e[M],ne[M],h[N];
int n,m,que[N],d[N];
bitset<N> f[N];

{
ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
d[b] ++;
}

void topsort()
{
int tt = -1,hh = 0;

for(int i = 1;i <= n;i ++)
if(!d[i])que[++ tt] = i;

while(hh <= tt)
{
int u = que[hh ++];
for(int i = h[u]; ~i ;i = ne[i])
{
int v = e[i];
d[v] --;
if(!d[v])que[++ tt] = v;
}
}
}

int main()
{
memset(h,-1,sizeof h);

cin >> n >> m;
for(int i = 1;i <= m;i ++)
{
int a,b;
scanf("%d%d",&a,&b);
}

topsort();

for(int i = n - 1; ~i ;i --)
{
int u = que[i];
f[u][u] = 1;
for(int i = h[u]; ~i ;i = ne[i])
{
int v = e[i];
f[u] |= f[v];
}
}

for(int i = 1;i <= n;i ++)
printf("%d\n",f[i].count());
}


2020-02-13 15:21
#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010,M = 20010;

int idx,e[M],ne[M],h[N];
int n,m,que[N],d[N],dis[N];

{
ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
d[b] ++;
}

void topsort()
{
int tt = -1,hh = 0;

for(int i = 1;i <= n;i ++)
if(!d[i])que[++ tt] = i;

while(hh <= tt)
{
int u = que[hh ++];
for(int i = h[u]; ~i ;i = ne[i])
{
int v = e[i];
d[v] --;
if(!d[v])que[++ tt] = v;
}
}
}

int main()
{
memset(h,-1,sizeof h);

cin >> n >> m;
for(int i = 1;i <= m;i ++)
{
int a,b;
scanf("%d%d",&a,&b);
}

topsort();

for(int i = 1;i <= n;i ++)
{
dis[i] = 100;
if(d[i]){puts("Poor Xed");return 0;}
}
for(int i = 0;i < n;i ++)
{
int u = que[i];
for(int i = h[u]; ~i ;i = ne[i])
{
int v = e[i];
dis[v] = max(dis[v],dis[u] + 1);
}
}

int res = 0;
for(int i = 1;i <= n;i ++)
res += dis[i];
cout << res;
}


2020-02-13 15:14
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110,M = N * N;

int n,idx,e[M],ne[M],h[N];
int que[N],d[N];

{
ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
d[b] ++;
}

void topsort()
{
int tt = -1,hh = 0;

for(int i = 1;i <= n;i ++)
if(!d[i])que[++ tt] = i;

while(hh <= tt)
{
int u = que[hh ++];
for(int i = h[u]; ~i ;i = ne[i])
{
int v = e[i];
d[v] --;
if(!d[v])que[++ tt] = v;
}
}
}

int main()
{
memset(h,-1,sizeof h);

cin >> n;
for(int i = 1;i <= n;i ++)
{
int son;
}

topsort();

for(int i = 0;i < n;i ++)
printf("%d ",que[i]);
}


2020-02-12 10:47

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 30;

int p[N];
int n,din[N],dout[N];
bool st[N];

int find(int x)
{
return x == p[x] ? x : find(p[x]);
}

int main()
{
int T;
cin >> T;
while(T --)
{
memset(din,0,sizeof din);
memset(dout,0,sizeof dout);
memset(st,0,sizeof st);
for(int i = 0;i < N;i ++)
p[i] = i;

scanf("%d",&n);
while(n --)
{
char str[1100];
scanf("%s",str);
int len = strlen(str);
int a = str[0] - 'a',b = str[len - 1] - 'a';
dout[a] ++,din[b] ++;
st[a] = st[b] = 1;
p[find(a)] = find(b);
}

int s = 0,e = 0;
bool success = 1;

for(int i = 0;i < 26;i ++)
if(din[i] != dout[i])
{
if(din[i] == dout[i] + 1)s ++;
else if(din[i] + 1 == dout[i])e ++;
else success = 0;
}

if(s == 0 && e == 0);
else if(s == 1 && e == 1);
else success = 0;

int reb = -1;
for(int i = 0;i < 26;i ++)
if(st[i])
{
if(reb == -1)reb = find(i);
else if(reb != find(i))success = 0;
}

if(success)puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
}


2020-02-12 10:25

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

int n = 500,m,g[N][N];
int d[N];
int ans[1100],cnt;

void dfs(int u)
{
for(int i = 1;i <= n;i ++)
if(g[u][i])
{
g[u][i] --,g[i][u] --;
dfs(i);
}

ans[++ cnt] = u;
}

int main()
{
cin >> m;
for(int i = 1;i <= m;i ++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x][y] ++,g[y][x] ++;
d[x] ++,d[y] ++;
}

int s = 1;
while(!d[s])s ++;
for(int i = 1;i <= n;i ++)
if(d[i] % 2)
{
s = i;
break;
}

dfs(s);

for(int i = cnt; i ;i --)
printf("%d\n",ans[i]);

return 0;
}



2020-02-10 14:43

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e5+5,M = 4e5 + 5;

int n,m,idx = 0,e[M],ne[M],h[N];
vector<int> ans;
int type,din[N],dout[N];
bool used[M];

{
ne[idx] = h[u];
e[idx] = v;
h[u] = idx ++;
}

void euler(int u)
{
for(int &i = h[u]; ~i ;)
{
if(used[i])
{
i = ne[i];
continue;
}

int v = e[i],t = i;
if(type == 1)used[i ^ 1] = 1;

i = ne[i];

euler(v);

if(type == 1)
{
if(t % 2)t = - (t / 2 + 1);
else t = t / 2 + 1;
}
else t ++;

ans.push_back(t);
}
}

int main()
{
cin >> type >> n >> m;
memset(h,-1,sizeof h);

int xi,yi;
for(int i = 1;i <= m;i ++)
{
scanf("%d%d",&xi,&yi);
din[yi] ++;
dout[xi] ++;
}

if(type == 1)
{
for(int i = 1;i <= n;i ++)
if((din[i] + dout[i]) % 2)
{
puts("NO");
return 0;
}
}
else
{
for(int i = 1;i <= n;i ++)
if(din[i] != dout[i])
{
puts("NO");
return 0;
}
}

for(int i = 1;i <= n;i ++)
if(h[i] != -1){euler(i);break;}

if(ans.size() != m)
{
puts("NO");
return 0;
}

puts("YES");
for(int i = ans.size()-1;i >= 0;i --)
printf("%d ",ans[i]);
}


2020-02-10 13:45

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
int x1,y1,x2,y2;
cin >> x1 >> y1;

double sum = 0;
while(cin >> x1 >> y1 >> x2 >> y2)
{
double dx = x1 - x2;
double dy = y1 - y2;
sum += sqrt(dx * dx + dy * dy) * 2;
}

int num = round(sum * 60 / 1000 / 20);

printf("%d:%02d",num / 60,num % 60);
}