oj.uz

답안 #541803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541803 2022-03-24T12:34:28 Z mat_v Logičari (COCI21_logicari) C++14
20 / 110
 170 ms 21376 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 dsu[100005];
int finddsu(int x){
    if(x == dsu[x])return x;
    return dsu[x] = finddsu(dsu[x]);
}

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);
    }
}


ll ans = 1e9;

int z1,z2;

bool bio[100005][2][2];
ll 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){
        ll 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){
        ll 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);
    ll 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;
    int idx = n;
    ff(i,1,n)dsu[i] = i;
    ff(i,1,n){
        int x,y;
        cin >> x >> y;
        int p1 = finddsu(x);
        int p2 = finddsu(y);
        if(p1 == p2){
            idx = i;
        }
        else{
            graf[x].pb(y);
            graf[y].pb(x);
            dsu[p1] = p2;
        }
        edges[i] = {x,y};
    }

    dfsdist(edges[idx].xx, 1);
    vector<int> braca;
    int tmp = edges[idx].yy;
    while(tmp != edges[idx].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:124:5: note: in expansion of macro 'ff'
  124 |     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:125:5: note: in expansion of macro 'ff'
  125 |     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:131:5: note: in expansion of macro 'ff'
  131 |     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:132:9: note: in expansion of macro 'ff'
  132 |         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:133:13: note: in expansion of macro 'ff'
  133 |             ff(k,0,1){
      |             ^~
Main.cpp:134:44: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  134 |                 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:151:5: note: in expansion of macro 'ff'
  151 |     ff(i,1,n)dsu[i] = i;
      |     ^~
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:152:5: note: in expansion of macro 'ff'
  152 |     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:183:5: note: in expansion of macro 'ff'
  183 |     ff(j,0,2){
      |     ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 143 ms 21376 KB Output is correct
6 Correct 170 ms 21068 KB Output is correct
7 Correct 146 ms 18668 KB Output is correct
8 Correct 144 ms 19272 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2684 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2684 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 2 ms 2772 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 143 ms 21376 KB Output is correct
6 Correct 170 ms 21068 KB Output is correct
7 Correct 146 ms 18668 KB Output is correct
8 Correct 144 ms 19272 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 2 ms 2684 KB Output is correct
17 Correct 2 ms 2692 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Incorrect 2 ms 2772 KB Output isn't correct
22 Halted 0 ms 0 KB -