oj.uz

Submission #541800

# Submission time Handle Problem Language Result Execution time Memory
541800 2022-03-24T12:22:43 Z mat_v Logičari (COCI21_logicari) C++14
10 / 110
 598 ms 524288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;
int m;
pii edges[100005];
vector<int> graf[100005];


int dist[100005];

void dfsdist(int x, int duz){
    dist[x] = duz;
    for(auto c:graf[x]){
        if(dist[c])continue;
        dfsdist(c, duz + 1);
    }
}


int ans = 1e9;

int z1,z2;

bool bio[100005][2][2];
int dp[100005][2][2];

void dfs(int x, int y, int z, int cale){
    if(z && (x == z1 || x == z2)){
        bio[x][y][z] = 1;
        dp[x][y][z] = 1e9;
        return;
    }
    if(bio[x][y][z])return;
    bio[x][y][z] = 1;
    for(auto c:graf[x]){
        if(c == cale)continue;
        dfs(c,0,0,x);
        dfs(c,0,1,x);
        dfs(c,1,0,x);
        dfs(c,1,1,x);
    }
    if(y == 0 && z == 0){
        int sum = 0;
        bool doso = 0;
        for(auto c:graf[x]){
            if(c == cale)continue;
            doso = 1;
            sum += dp[c][0][0];
        }
        if(!doso){
            dp[x][y][z] = 1e9;
            return;
        }
        dp[x][y][z] = 1e9;
        for(auto c:graf[x]){
            if(c == cale)continue;
            dp[x][y][z] = min(dp[x][y][z], sum - dp[c][0][0] + dp[c][0][1]);
        }
    }
    if(y == 0 && z == 1){
        int sum = 0;
        bool doso = 0;
        for(auto c:graf[x]){
            if(c == cale)continue;
            doso = 1;
            sum += dp[c][1][0];
        }
        if(!doso){
            dp[x][y][z] = 1e9;
            return;
        }
        dp[x][y][z] = 1e9;
        for(auto c:graf[x]){
            if(c == cale)continue;
            dp[x][y][z] = min(dp[x][y][z], sum-dp[c][1][0]+dp[c][1][1]);
        }
        dp[x][y][z]++;
    }
    if(y == 1 && z == 0){
        dp[x][y][z] = 0;
        for(auto c:graf[x]){
            if(c == cale)continue;
            dp[x][y][z] += dp[c][0][0];
        }
    }
    if(y == 1 && z == 1){
        dp[x][y][z] = 1;
        for(auto c:graf[x]){
            if(c == cale)continue;
            dp[x][y][z] += dp[c][1][0];
        }
    }
}

void resi(int f1, int f2){
    z1 = f1;
    z2 = f2;
    ff(i,1,n)graf[i].clear();
    ff(i,1,n){
        if(edges[i].xx == f1 && edges[i].yy == f2)continue;
        if(edges[i].yy == f1 && edges[i].xx == f2)continue;
        graf[edges[i].xx].pb(edges[i].yy);
        graf[edges[i].yy].pb(edges[i].xx);
    }
    ff(i,1,n){
        ff(j,0,1){
            ff(k,0,1){
                bio[i][j][k] = dp[i][j][k] = 0;
            }
        }
    }
    dfs(1,0,1,0);
    dfs(1,0,0,0);
    int sta = min(dp[1][0][1], dp[1][0][0]);
    if(sta < 1e9)ans = min(ans, sta);
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    ff(i,1,n){
        int x,y;
        cin >> x >> y;
        edges[i] = {x,y};
        if(i < n){
            graf[x].pb(y);
            graf[y].pb(x);
        }
    }

    dfsdist(edges[n].xx, 1);
    vector<int> braca;
    int tmp = edges[n].yy;
    while(tmp != edges[n].xx){
        braca.pb(tmp);
        for(auto c:graf[tmp]){
            if(dist[c] < dist[tmp]){
                tmp = c;
                break;
            }
        }
    }
    braca.pb(tmp);

    int m = braca.size();
    ff(j,0,2){
        resi(braca[j%m],braca[(j+1)%m]);
    }
    if(ans >= n+5)ans = -1;
    cout << ans << "\n";

    return 0;
}

Compilation message

Main.cpp: In function 'void resi(int, int)':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:118:5: note: in expansion of macro 'ff'
  118 |     ff(i,1,n)graf[i].clear();
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,1,n){
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:125:5: note: in expansion of macro 'ff'
  125 |     ff(i,1,n){
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:126:9: note: in expansion of macro 'ff'
  126 |         ff(j,0,1){
      |         ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:127:13: note: in expansion of macro 'ff'
  127 |             ff(k,0,1){
      |             ^~
Main.cpp:128:44: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  128 |                 bio[i][j][k] = dp[i][j][k] = 0;
      |                                ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:144:5: note: in expansion of macro 'ff'
  144 |     ff(i,1,n){
      |     ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:169:5: note: in expansion of macro 'ff'
  169 |     ff(j,0,2){
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 128 ms 20556 KB Output is correct
6 Correct 127 ms 20304 KB Output is correct
7 Correct 132 ms 17896 KB Output is correct
8 Correct 127 ms 18456 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 598 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 598 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 128 ms 20556 KB Output is correct
6 Correct 127 ms 20304 KB Output is correct
7 Correct 132 ms 17896 KB Output is correct
8 Correct 127 ms 18456 KB Output is correct
9 Runtime error 598 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -