Submission #367269

#	Time	Username	Problem	Language	Result	Execution time	Memory
367269		Sparky_09	Ideal city (IOI12_city)	C++17	100 / 100	569 ms	19816 KiB

city

#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

template <class T>
void rd(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void wr(T x) {
	if (x < 0) putchar('-'), wr(-x);
	else if (x < 10) putchar(x + '0');
	else wr(x / 10), putchar(x % 10 + '0');
}
void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
/*
  think of it as a tree
  we dont need to acc for each node
  we keep track of hor and ver
  for children of node
  we add child dist + (sum of alldist without that child)
  dist can be split as hor and ver can be handled separately 
  but how to implement
  because dist remains const 
  we use that fact
  how to maintain cleanly
  each node can go hor or ver
  if both hor ver or other sides then treat each as subtree
  for each node we keep count of vals coming to it
  so we can add those to our subtree
  dist trav hor dist trav ver is the parent stuff
  but at each node we need to add 1 + 2 + 3 - - - n
  n(n+1)/2 added each time?
  no
  at each level theres certain number of nodes
  so we need to somehow take that into account
  when we go down ver
  we have to add it num of times we visited it horizontally
  when we go down more we just add hor to it that will take in account the going down
  by 1 vertically
  work backwards?
  hor tree ver tree
*/

const int maxn = 1e5 + 5, MOD = 1e9;;
vector<pair<int, int>> a;
ll ans = 0, n;
int tls[maxn], csize[maxn];
multiset<int> adj[maxn];
vector<bool> vis(maxn, 0);
 
void dfs(int u){
    vis[u] = 1;
    //cerr << u << '\n';
    for(auto c : adj[u]){
        if(!vis[c]){
            dfs(c);
            csize[u] += csize[c];
        }
    }
    ans = (ans + (1ll * csize[u] * (n - csize[u])) % MOD) % MOD;
}
void solve(){
    int i = 0, m = 0;
    sort(a.begin(),a.end());
    rep(i, 0, n){
      adj[i].clear();
    }
    while(i < n){
        int j = i + 1; tls[i] = m;
        while(j < n and a[j] == make_pair(a[j - 1].first, a[j - 1].second + 1)){
        		//cerr << j << ' ' << tls[j] << ' ' << m << '\n';
        		tls[j++] = m;
        }	
        csize[m] = j - i; i = j;
        //cerr << i << ' ' << csize[m] << '\n';
        m++;
    }
    cerr << "hello";
    int j = 0;
    rep(i, 0, n){
        for(; j < n and a[j] < make_pair(a[i].first - 1 , a[i].second); j++){cerr<<"hi";}
        if(j < n and a[j] == make_pair(a[i].first - 1 , a[i].second)){
        		//cerr << tls[i] << " -> " << tls[j] << '\n';
            adj[tls[i]].insert(tls[j]);
            adj[tls[j]].insert(tls[i]);
        }
    }
    rep(i, 0, (int)vis.size()){
      vis[i] = 0;
    }
    dfs(0);
}
 
int DistanceSum(int N, int *X, int *Y) {
    n = N;
    rep(i, 0, n){
      a.emplace_back(X[i], Y[i]);
    }
    solve();
    rep(i, 0, n){
      //easy way to do it is to just rev coord
      //a[i].first = 
      swap(a[i].first,a[i].second);
    }
    solve();
    return ans % MOD;
}
/*
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif

}
*/

Compilation message (stderr)

city.cpp: In function 'void usaco(std::string)':
city.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45