| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61460 |
2018-07-26T04:40:34 Z |
koosaga(#1775) |
Min-max tree (BOI18_minmaxtree) |
C++11 |
|
726 ms |
21592 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 70005;
int n, m;
vector<int> gph[MAXN];
map<int, int> mp;
int dep[MAXN], par[17][MAXN];
int emax[MAXN], emin[MAXN], cost[MAXN];
int s[MAXN], e[MAXN];
void dfs(int x, int p){
for(auto &i : gph[x]){
if(i != p){
dep[i] = dep[x] + 1;
par[0][i] = x;
dfs(i, x);
}
}
}
int lca(int s, int e){
if(dep[s] > dep[e]) swap(s, e);
int dx = dep[e] - dep[s];
for(int i=0; i<17; i++){
if((dx >> i) & 1) e = par[i][e];
}
for(int i=16; i>=0; i--){
if(par[i][s] != par[i][e]){
s = par[i][s];
e = par[i][e];
}
}
if(s != e) return par[0][s];
return s;
}
struct bipartite_matching{
vector<int> gph[MAXN];
int l[MAXN], r[MAXN];
void init(){
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
}
void add_edge(int s, int e){
gph[s].push_back(e);
}
bool vis[MAXN];
bool dfs(int x){
if(vis[x]) return 0;
vis[x] = 1;
for(auto &i : gph[x]){
if(r[i] == -1 || dfs(r[i])){
r[i] = x;
l[x] = i;
return 1;
}
}
return 0;
}
void match(int k){
for(int i=0; i<k; i++){
if(l[i] == -1){
memset(vis, 0, sizeof(vis));
dfs(i);
}
}
}
}bpm;
int main(){
scanf("%d",&n);
for(int i=0; i<n-1; i++){
scanf("%d %d",&s[i],&e[i]);
gph[s[i]].push_back(e[i]);
gph[e[i]].push_back(s[i]);
}
dfs(1, -1);
for(int i=1; i<17; i++){
for(int j=1; j<=n; j++){
par[i][j] = par[i-1][par[i-1][j]];
}
}
bpm.init();
memset(emin, -1, sizeof(emin));
memset(emax, 0x3f, sizeof(emax));
scanf("%d",&m);
for(int i=0; i<m; i++){
char buf[5];
int s, e, x;
scanf("%s %d %d %d",buf,&s,&e,&x);
cost[i] = x;
mp[x] = i;
int l = lca(s, e);
if(*buf == 'M'){
for(int j=s; j!=l; j=par[0][j]){
emax[j] = min(emax[j], x);
}
for(int j=e; j!=l; j=par[0][j]){
emax[j] = min(emax[j], x);
}
}
else{
for(int j=s; j!=l; j=par[0][j]){
emin[j] = max(emin[j], x);
}
for(int j=e; j!=l; j=par[0][j]){
emin[j] = max(emin[j], x);
}
}
}
for(int i=2; i<=n; i++){
int l = -1, r = -1;
if(mp.find(emin[i]) != mp.end()) l = mp[emin[i]];
if(mp.find(emax[i]) != mp.end()) r = mp[emax[i]];
if(~l) bpm.add_edge(l, i-2);
if(~r) bpm.add_edge(r, i-2);
}
bpm.match(m);
// l : left -> right fun
// r : right -> left fun
for(int i=0; i<n-1; i++){
printf("%d %d ", s[i], e[i]);
if(bpm.r[i] == -1) printf("%d\n", emin[i]);
else printf("%d\n", cost[bpm.r[i]]);
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
minmaxtree.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s[i],&e[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
~~~~~^~~~~~~~~
minmaxtree.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s %d %d %d",buf,&s,&e,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
726 ms |
21592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
21592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
