| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 585647 |
2022-06-29T07:21:53 Z |
조영욱(#8387) |
Star Trek (CEOI20_startrek) |
C++17 |
|
53 ms |
3444 KB |
#include <bits/stdc++.h>
using namespace std;
int n;
long long d;
const int mod=1e9+7;
long long fastpow(long long a,long long b) {
if (b==0) {
return 1;
}
if (b%2==1) {
return (fastpow(a,b-1)*a)%mod;
}
long long half=fastpow(a,b/2);
return (half*half)%mod;
}
vector<int> adj[100001];
int dp[100001];
int dp1[100001];
int dep[100001];
void dfs1(int v,int prev) {
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev){
continue;
}
dep[nt]=dep[v]+1;
dfs1(nt,v);
if (dp[nt]==0) {
dp[v]++;
}
}
}
void dfs2(int v,int prev) {
if (prev==0) {
dp1[v]=1;
}
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
if (dp[v]<=1) {
dp1[nt]=2-dp1[v];
}
else {
dp1[nt]=0;
}
dfs2(nt,v);
}
}
void dfs3(int v,int prev) {
if (prev==0) {
dp1[v]=0;
}
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
if (dp[v]<=1) {
dp1[nt]=1-dp1[v];
}
else {
dp1[nt]=0;
}
dfs3(nt,v);
}
}
long long d1,d2,d3,d4;
long long one,two,three,four;
int main(void) {
scanf("%d %lld",&n,&d);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
long long s=0;
dfs1(1,0);
dfs3(1,0);
for(int i=1;i<=n;i++) if (dp[i]!=0||dp1[i]!=0) { s++;}
//printf("%lld\n",s);
for(int i=1;i<=n;i++) {
memset(dp,0,sizeof(dp));
memset(dp1,0,sizeof(dp1));
dep[i]=0;
dfs1(i,0);
dfs2(i,0);
for(int j=1;j<=n;j++) {
if (dp[j]>0) {
d1++;
if (j==1) one++;
}
else if (i==j) {
d3++;
if (j==1) three++;
}
else if (dp1[j]==2) {
d1++;
if (j==1) one++;
}
else if (dp1[j]==0) {
d2++;
if (j==1) two++;
}
else {
if (dep[i]%2==dep[j]%2) {
d3++;
if (j==1) three++;
}
else {
d4++;
if (j==1) four++;
}
}
//printf("%d %d %d %d %d %d\n",i,j,one,two,three,four);
}
}
//printf("%lld %lld %lld %lld\n",one,two,three,four);
long long ret=n*one+four*s+three*(n-s);
printf("%lld",ret);
}
Compilation message
startrek.cpp: In function 'void dfs1(int, int)':
startrek.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
startrek.cpp: In function 'void dfs2(int, int)':
startrek.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
startrek.cpp: In function 'void dfs3(int, int)':
startrek.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
startrek.cpp: In function 'int main()':
startrek.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d %lld",&n,&d);
| ~~~~~^~~~~~~~~~~~~~~~~
startrek.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
3444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
3444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
