oj.uz

Submission #270445

# Submission time Handle Problem Language Result Execution time Memory
270445 2020-08-17T15:39:15 Z stoyan_malinin Training (IOI07_training) C++14
82 / 100
 300 ms 21788 KB 
#include <tuple>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 1005;
const int MAXLog = 20;
const long long inf = 1e15 + 5;

struct Path
{
    int cost;
    vector <int> part[2];

    long long pathAddition;

    Path(){}
    Path(int cost)
    {
        this->pathAddition = -1;
        this->cost = cost;
    }
};

int n, m;
vector <int> graph[MAXN];
vector <Path> node2Paths[MAXN];

int parentInd[MAXN];
int sparse[25][MAXN];
int parent[MAXN], depth[MAXN];

long long memo[MAXN][(1<<11)+5];

void DFSInit(int x, int last, int level)
{
    depth[x] = level;
    parent[x] = last;

    for(int i = 0;i<graph[x].size();i++)
    {
        if(graph[x][i]==last)
        {
            graph[x].erase(graph[x].begin()+i);
            break;
        }
    }

    for(int i = 0;i<graph[x].size();i++)
    {
        parentInd[ graph[x][i] ] = i;
    }

    for(int y: graph[x])
    {
        DFSInit(y, x, level+1);
    }
}

int findLCA(int u, int v)
{
    if(depth[u]>depth[v]) swap(u, v);

    for(int i = MAXLog;i>=0;i--)
    {
        if(sparse[i][v]!=-1 && depth[ sparse[i][v] ]>=depth[u])
        {
            v = sparse[i][v];
        }
    }

    if(u==v) return u;
    for(int i = MAXLog;i>=0;i--)
    {
        if(sparse[i][u]!=sparse[i][v])
        {
            u = sparse[i][u];
            v = sparse[i][v];
        }
    }

    return parent[u];
}

int getDist(int u, int v)
{
    return depth[u] + depth[v] - 2*depth[findLCA(u, v)];
}

void init(vector <tuple <int, int, int>> &rawPaths)
{
    DFSInit(1, -1, 1);
    for(int x = 1;x<=n;x++) sparse[0][x] = parent[x];
    for(int i = 1;i<=MAXLog;i++)
    {
        for(int x = 1;x<=n;x++)
        {
            if(sparse[i-1][x]==-1) sparse[i][x] = -1;
            else sparse[i][x] = sparse[i-1][ sparse[i-1][x] ];
        }
    }

    for(tuple <int, int, int> t: rawPaths)
    {
        int u = get<0>(t);
        int v = get<1>(t);
        int c = get<2>(t);
        if(getDist(u, v)%2==1) continue;

        //cout << u << " " << v << " -> lca:-" << findLCA(u, v) << '\n';

        Path p(c);
        int lca = findLCA(u, v);

        int x = u;
        while(x!=lca) p.part[0].push_back(x), x = parent[x];

        x = v;
        while(x!=lca) p.part[1].push_back(x), x = parent[x];

        node2Paths[lca].push_back(p);
    }

    memset(memo, -1, sizeof(memo));
}

bool isCompatable(int x, int mask, Path &p)
{
    bool fail = false;
    for(int ind = 0;ind<2;ind++)
    {
        if(p.part[ind].size()>0 && ((mask>>parentInd[ p.part[ind].back() ])&1)==1) fail = true;
    }

    if(fail==false) return true;
    return false;
}

bool checkCycle(int x, int mask)
{
    for(Path p: node2Paths[x])
    {
        if(isCompatable(x, mask, p)==true) return true;
    }

    return false;
}

int updateMask(int mask, Path &p)
{
    for(int ind = 0;ind<2;ind++)
    {
        if(p.part[ind].size()==0) continue;
        mask |= (1<<parentInd[ p.part[ind].back() ]);
    }

    return mask;
}

long long rec(int x, int mask)
{
    if(graph[x].size()==0) return 0;
    if(memo[x][mask]!=-1) return memo[x][mask];

    long long answer = 0;
    for(Path p: node2Paths[x])
    {
        if(isCompatable(x, mask, p)==false) continue;
        int newMask = updateMask(mask, p);

        long long curr = p.cost + rec(x, newMask);

        if(p.pathAddition==-1)
        {
            p.pathAddition = 0;
            for(int ind = 0;ind<2;ind++)
            {
                int last = -1;
                for(int x: p.part[ind])
                {
                    p.pathAddition += rec(x, ((last==-1)?0:(1<<parentInd[last])));
                    last = x;
                }
            }
        }
        curr += p.pathAddition;

        answer = max(answer, curr);
    }

    long long curr = 0;
    for(int i = 0;i<graph[x].size();i++)
    {
        if(((mask>>i)&1)==1) continue;
        curr += rec(graph[x][i], 0);
    }
    answer = max(answer, curr);

    //cout << x << " " << mask << " -> " << answer << '\n';

    memo[x][mask] = answer;
    return answer;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    long long sumAllEdges = 0;
    vector <tuple <int, int, int>> rawPaths;

    for(int i = 0;i<m;i++)
    {
        int x, y, c;
        cin >> x >> y >> c;

        if(c==0)
        {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        else
        {
            sumAllEdges += c;
            rawPaths.push_back(make_tuple(x, y, c));
        }
    }

    init(rawPaths);
    cout << sumAllEdges - rec(1, 0) << '\n';
}

Compilation message

training.cpp: In function 'void DFSInit(int, int, int)':
training.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0;i<graph[x].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
training.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0;i<graph[x].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
training.cpp: In function 'long long int rec(int, int)':
training.cpp:194:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     for(int i = 0;i<graph[x].size();i++)
      |                   ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16640 KB Output is correct
2 Correct 8 ms 16640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18176 KB Output is correct
2 Correct 19 ms 18304 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16640 KB Output is correct
2 Correct 8 ms 16640 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16640 KB Output is correct
2 Correct 9 ms 16640 KB Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17020 KB Output is correct
2 Correct 15 ms 16896 KB Output is correct
3 Correct 196 ms 17024 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17408 KB Output is correct
2 Correct 139 ms 17196 KB Output is correct
3 Correct 30 ms 17400 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16896 KB Output is correct
2 Correct 17 ms 17312 KB Output is correct
3 Execution timed out 1091 ms 21756 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18680 KB Output is correct
2 Execution timed out 840 ms 21788 KB Time limit exceeded
3 Halted 0 ms 0 KB -