oj.uz

Submission #79510

# Submission time Handle Problem Language Result Execution time Memory
79510 2018-10-15T00:07:52 Z AngelKnows Network (BOI15_net) C++14
0 / 100
 2 ms 508 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=500000+10;
const double eps=1e-5;
const int mo=1e9+7;

int n;
struct edge {
	int to,nxt;
} e[2*N];
int head[N];
int tot;
int d[N];
int cnt;
int leaves[N];
void insert(int x,int y) {
	e[++tot].to=y,e[tot].nxt=head[x],head[x]=tot;
	e[++tot].to=x,e[tot].nxt=head[y],head[y]=tot;
}
void dfs(int x,int fa) {
	int y;
	bool leaf=1;
	for (int i=head[x];i;i=e[i].nxt) {
		y=e[i].to;
		if (y!=fa) {
			dfs(y,x);
			leaf=0;
		}
	}
	cnt+=leaf;
	if (leaf) leaves[cnt]=x;
}
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    int x,y;
    FOR(i,n-1) {
    	scanf("%d %d",&x,&y);
    	++d[x],++d[y];
    	insert(x,y);
	}
	int root=0;
	FOR(i,n) if (d[i]!=1) {
		dfs(i,0);
		root=i;
		break;
	}
	int ans=(cnt-1)/2+1;
	printf("%d\n",ans);
	for (int i=1;i<=cnt;i+=2) {
		if (i==cnt) {
			printf("%d %d\n",leaves[i],root);
		} else printf("%d %d\n",leaves[i],leaves[i+1]);
	}
	return 0;
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
net.cpp:58:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d",&x,&y);
      ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -