oj.uz

Submission #262773

# Submission time Handle Problem Language Result Execution time Memory
262773 2020-08-13T08:38:57 Z 반딧불(#5089) Training (IOI07_training) C++17
100 / 100
 47 ms 22264 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, y, c;
    dat(){}
    dat(int x, int y, int c): x(x), y(y), c(c){}
};

int n, m;
int sum;
vector<int> link[1002];
vector<dat> vec;
int DP[1002][1024];
vector<int> child[1002];
int childCount[1002];

int edgeIdx[1002][1002];

int depth[1002], par[1002];
int LCADB[1002][10];
bool visited[1002];

vector<int> edgeList[1002];
vector<vector<pair<int, int> > > checkList;
vector<int> key, edgeVal;

void dfs1(int x, int p = 0){
    for(auto &y: link[x]){
        if(p==y) continue;
        depth[y] = depth[x] + 1;
        par[y] = x;
        child[x].push_back(y);
        edgeIdx[x][y] = edgeIdx[y][x] = childCount[x]++;

        dfs1(y, x);
    }
}

void makeLCATable(){
    for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<10; d++){
        for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
    }
}

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<10; d++) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=9; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

void track(int x){
    visited[x] = 1;
    for(auto &y: child[x]){
        if(!visited[y]) track(y);
    }

    for(auto &i: edgeList[x]){
        for(auto &tmp: checkList[i]){
            edgeVal[i] += DP[tmp.first][tmp.second];
        }
    }

    for(int i=1; i<(1<<childCount[x]); i++){
        for(int j=0; j<childCount[x]; j++){
            if(i&(1<<j)){
                int tmp = child[x][j];
                DP[x][i] = max(DP[x][i], DP[x][i-(1<<j)] + DP[tmp][(1<<childCount[tmp])-1]);
            }
        }

        for(auto &j: edgeList[x]){
            if((i & key[j]) != key[j]) continue;
            DP[x][i] = max(DP[x][i], DP[x][i^key[j]] + edgeVal[j] + vec[j].c);
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        if(c == 0){
            link[u].push_back(v);
            link[v].push_back(u);
        }
        else{
            vec.push_back(dat(u, v, c));
            sum += c;
        }
    }
    edgeVal.resize(vec.size());

    dfs1(1);
    makeLCATable();

    for(int i=0; i<(int)vec.size(); i++){
        checkList.push_back({});
        key.push_back(0);

        if(abs(depth[vec[i].x] - depth[vec[i].y]) % 2 == 1) continue;
        int x = vec[i].x, y = vec[i].y;
        int z = getLCA(x, y);
        edgeList[z].push_back(i);

        if(x != z) checkList[i].push_back({x, (1<<childCount[x]) - 1});
        if(y != z) checkList[i].push_back({y, (1<<childCount[y]) - 1});

        while(x != z && par[x] != z){
            int px = par[x], nx = edgeIdx[x][px];
            checkList[i].push_back({px, (1<<childCount[px]) - 1 - (1<<nx)});
            x = px;
        }
        if(x != z) key.back() |= (1<<edgeIdx[x][z]);

        x = y;
        while(x != z && par[x] != z){
            int px = par[x], nx = edgeIdx[x][px];
            checkList[i].push_back({px, (1<<childCount[px]) - 1 - (1<<nx)});
            x = px;
        }
        if(x != z) key.back() |= (1<<edgeIdx[x][z]);
    }

    track(1);
    printf("%d", sum - DP[1][(1<<childCount[1]) - 1]);
}

Compilation message

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

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 2 ms 896 KB Output is correct
2 Correct 2 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12160 KB Output is correct
2 Correct 17 ms 12672 KB Output is correct

Subtask #4
7.0 / 7.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 #5
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 #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct
3 Correct 8 ms 4312 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6656 KB Output is correct
2 Correct 11 ms 4992 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 7 ms 4736 KB Output is correct
3 Correct 45 ms 22264 KB Output is correct
4 Correct 10 ms 5888 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10368 KB Output is correct
2 Correct 47 ms 22264 KB Output is correct
3 Correct 21 ms 10240 KB Output is correct
4 Correct 14 ms 5376 KB Output is correct