Submission #300730

#	Time	Username	Problem	Language	Result	Execution time	Memory
300730		BeanZ	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	1 / 100	5072 ms	46972 KiB

joitter2

// I_LOVE_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 2e3 + 5;
ll dp[N][N], tmp[N][N];
ll ans = 0;
ll n;
void construct(ll u, ll v){
        vector<pair<ll, ll>> mem;
        if (tmp[u][v] == 0) ans++;
        if (dp[v][u]){
                for (int j = 1; j <= n; j++){
                        if (j == u || j == v) continue;
                        ll cost = 0;
                        cost = cost + dp[j][u];
                        cost = cost + dp[j][v];
                        if (cost == 1){
                                if (dp[j][u] == 0 && tmp[j][u] == 0) ans++, tmp[j][u] = 1, mem.push_back({j, u});
                                if (dp[j][v] == 0 && tmp[j][v] == 0) ans++, tmp[j][v] = 1, mem.push_back({j, v});
                        }
                }
        }
        for (int j = 1; j <= n; j++){
                if (u == j || v == j) continue;
                if (dp[v][j] && dp[j][v] && tmp[u][j] == 0){
                        ans++;
                        tmp[u][j] = 1;
                        mem.push_back({u, j});
                }
        }
        tmp[u][v] = 1;
        dp[u][v] = 1;
        for (auto j : mem){
                construct(j.first, j.second);
        }
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.out", "w", stdout);
        }
        ll m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++){
                ll u, v;
                cin >> u >> v;
                construct(u, v);
                cout << ans << endl;
        }
}
/*
*/

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:45:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   45 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:46:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |                 freopen("test.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83