oj.uz

Submission #54620

# Submission time Handle Problem Language Result Execution time Memory
54620 2018-07-04T08:22:53 Z 노영훈(#1490) Training (IOI07_training) C++11
30 / 100
 19 ms 1004 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=5010, inf=2e9;

int n, m;

vector<int> G[MX];

struct edge {
    int u, v, c;
    void scan(){
        cin>>u>>v>>c;
        if(c==0){
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
} E[MX];

int dep[MX], now, par[MX];

void dfs1(int v, int p){
    dep[v]=++now, par[v]=p;
    for(int x:G[v]){
        if(x==p) continue;
        dfs1(x,v);
    }
    now--;
}

int dist(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    int res=0;
    while(dep[u]>dep[v]) u=par[u], res++;
    while(u!=v) u=par[u], v=par[v], res+=2;
    return res;
}
int lca(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]>dep[v]) u=par[u];
    while(u!=v) u=par[u], v=par[v];
    return u;
}

vector<int> R[MX];

int D[MX][11];

int which(int v, int x){
    if(x==0) return 0;
    for(int i=0; i<(int)G[v].size(); i++)
        if(G[v][i]==x) return i+1;
    return 0;
}

bool valid(int e, int x, int v){
    int a=E[e].u, b=E[e].v;
    while(a!=v) if(a==x) return false; else a=par[a];
    while(b!=v) if(b==x) return false; else b=par[b];
    return true;
}

int d(int v, int out){
    int &res=D[v][out];
    if(res>=0) return res;
    res=0;
    if(out>0) out=G[v][out-1];

    for(int x:G[v]){
        if(x==par[v] || x==out) continue;
        res+=d(x,0);
    }

    for(int e:R[v]){
        if(!valid(e,out,v)) continue;
        
        int now=E[e].c;
        int a=E[e].u, b=E[e].v;

        int prv=0;
        while(a!=v){
            now+=d(a, which(a,prv));
            if(par[a]==v) break;
            prv=a; a=par[a];
        }
        prv=0;
        while(b!=v){
            now+=d(b, which(b,prv));
            if(par[b]==v) break;
            prv=b; b=par[b];
        }

        for(int x:G[v]){
            if(x==a || x==b || x==out || x==par[v]) continue;
            now+=d(x, 0);
        }

        res=max(res, now);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) E[i].scan();

    dfs1(1,-1);

    ll ans=0;

    for(int i=1; i<=m; i++){
        if(E[i].c==0) continue;
        int u=E[i].u, v=E[i].v;
        if(dist(u,v)%2==1){
            ans+=E[i].c; E[i].c=0;
        }
    }


    for(int i=1; i<=m; i++){
        if(E[i].c==0) continue;
        int x=lca(E[i].u, E[i].v);
        R[x].push_back(i);
        ans+=E[i].c;
    }
    
    for(int i=1; i<=n; i++)
        for(int j=0; j<=10; j++)
            D[i][j]=-1;
/*


    for(int i=1; i<=n; i++, cout<<'\n')
        for(int j=-1; j<=10; j++)
            cout<<G[i][j]<<' ';
    cout<<'\n';

    for(int i=1; i<=n; i++, cout<<'\n')
        for(int j=0; j<=10; j++)
            cout<<d(i,j)<<' ';
*/

    cout<<ans-d(1,0);

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 2 ms 664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 920 KB Output is correct
2 Correct 12 ms 932 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -