oj.uz

Submission #262750

# Submission time Handle Problem Language Result Execution time Memory
262750 2020-08-13T08:10:33 Z 문홍윤(#5091) Training (IOI07_training) C++17
100 / 100
 14 ms 4736 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF=1e9;

int n, m, link[1010][12], sz[1010], p[1010], d[1010], rv[1010], ans;
vector<int> gph[1010], lc[1010];
pair<pii, int> edg[5010];

void dfs(int num, int par){
    d[num]=d[par]+1;
    p[num]=par;
    for(auto i:gph[num]){
        if(i==par)continue;
        link[num][sz[num]++]=i;
        rv[i]=sz[num]-1;
        dfs(i, num);
    }
}
int lca(int a, int b){
    if(d[a]<d[b])swap(a, b);
    while(d[a]>d[b])a=p[a];
    while(a!=b)a=p[a], b=p[b];
    return a;
}

int dp[1010][1050];

int get_dp(int a, int b, int c){
    if(d[a]<d[b])swap(a, b);
    int ret=0, ba=0, bb=0;
    while(d[a]>d[b]){
        int mask=(1<<sz[a])-1-(1<<rv[ba]);
        if(!ba)mask+=(1<<rv[ba]);
        ret+=dp[a][mask];
        ba=a;
        a=p[a];
    }
    while(a!=b){
        int mask=(1<<sz[a])-1-(1<<rv[ba]);
        if(!ba)mask+=(1<<rv[ba]);
        ret+=dp[a][mask];
        mask=(1<<sz[b])-1-(1<<rv[bb]);
        if(!bb)mask+=(1<<rv[bb]);
        ret+=dp[b][mask];
        ba=a;
        a=p[a];
        bb=b;
        b=p[b];
    }
    int msk=(1<<rv[ba])+(1<<rv[bb]);
    if(!ba)msk-=(1<<rv[ba]);
    if(!bb)msk-=(1<<rv[bb]);
    dp[a][msk]=max(dp[a][msk], ret+c);
    return msk;
}

vector<int> pc[12][12];

void dfs2(int num){
    for(int i=0; i<sz[num]; i++)dfs2(link[num][i]);
    vector<int> vc;
    for(int i=0; i<sz[num]; i++){
        int tmp=link[num][i];
        dp[num][1<<i]=dp[tmp][(1<<sz[tmp])-1];
        vc.eb(1<<i);
    }
    for(auto i:lc[num]){
        int mask=get_dp(edg[i].F.F, edg[i].F.S, edg[i].S);
        vc.eb(mask);
    }
    for(int i=1; i<=sz[num]; i++){
        for(auto j:pc[sz[num]][i]){
            for(auto k:vc){
                if(j&k)continue;
                dp[num][j|k]=max(dp[num][j|k], dp[num][j]+dp[num][k]);
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &edg[i].F.F, &edg[i].F.S, &edg[i].S);
        if(!edg[i].S){
            gph[edg[i].F.F].eb(edg[i].F.S);
            gph[edg[i].F.S].eb(edg[i].F.F);
        }
        ans+=edg[i].S;
    }
    for(int i=1; i<=11; i++){
        for(int j=1; j<(1<<i); j++){
            pc[i][__builtin_popcount(j)].eb(j);
        }
    }
    dfs(1, 0);
    for(int i=1; i<=m; i++){
        if((d[edg[i].F.F]+d[edg[i].F.S])%2==0)lc[lca(edg[i].F.F, edg[i].F.S)].eb(i);
    }
    dfs2(1);
    printf("%d", ans-dp[1][(1<<sz[1])-1]);
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
training.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         scanf("%d %d %d", &edg[i].F.F, &edg[i].F.S, &edg[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4608 KB Output is correct
2 Correct 8 ms 4736 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1024 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 7 ms 1664 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2176 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 14 ms 4608 KB Output is correct
4 Correct 4 ms 1792 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2176 KB Output is correct
2 Correct 14 ms 4608 KB Output is correct
3 Correct 11 ms 1792 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct