Областная олимпиада по информатике 2019 год

Задача F. Yosik - город где сбываются мечты

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Yosik - это город Казахстана где сбываются мечты миллионов. И при этом Yosik - важнейший экономический центр всего мира. Yosik, наряду с Лондоном и Токио, называют одним из трёх основных центров мировой экономики. Ну конечно же, без мэра CMaster город не был бы таким популярным. Он приложил все свои усилия чтобы достичь этого. Но экономическая война между другими странами повлиял негативно на экономику Yosik-a. Мэр хочет улучшить качество некоторых дорог в городе. И в городе существует $n$ районов. Каждый район имеет экономический статус: Высокий или Низкий. И чтобы мэр CMaster принял правильное решение об улучшении дорог во время кризиса в городе он должен узнать сколько пар Высоких важности районов это дорога соединяет. То есть, дорога соединяет два Высоких важности районов $(a, b)$ если и только если все пути между этими двумя районами проходят через эту дорогу. И есть $q$ событии двух видов: 1) Сделать статус района $v$ $(1 <=q v <=q n)$ Высоким если он Низкий, а иначе сделать его Низким. 2) Для дороги $i$ сказать количество пар районов $(a, b)$ с Высоким статусом что дорога $(1 <=q i <=q m)$ лежит на всех путях между этими районами $(a, b)$. И при этом пары $(a, b)$ и $(b, a)$ считаются одинаковыми Город можно представить как связный неориентированный граф с $n$ вершинами и $m$ ребрами. Где вершина это район а ребро это дорога. Каждый район имеет статус экономического важности либо Высокий либо Низкий. Вначале все районы имеют Низкий важность для экономики. Из района может существовать дорога которая соединяет район с собой (петля), но не существует кратные ребра, то есть дороги которые соединяют одинаковую пар вершин.

Формат входного файла

На первой строке даны 3 числа $n$, $m$ и $q$, количество районов, дорог и событии, соответственно. Далее следует $m$ чисел - неориентированные ребра в Yosik-e. В графе не существует две одинаковых ребер, но могут быть петли Потом вам дается запросы в виде $(type, number)$. Если $type = 1$, то это первый тип запросов и $number$ означает номер вершины, $(1 <=q number <=q n)$. А если $type = 2$, то это второй тип запросов и число означает номер ребра в порядке входных данных, $(1 <=q number <=q m)$

Формат выходного файла

Для каждого запроса вида 2, вы должны вывести количество пар город $(a, b)$ которые имеют статус Высокой важности что ребро $i$ лежит на всех путях между этими вершинами $(a, b)$

Система оценки

Данная задача содержит четыре подзадач: 1. $1 <=q n, q <=q 10$. Подзадача оценивается в 10 баллов 2. $1 <=q n, m, q <=q 300$. Подзадача оценивается в 14 баллов 3. $1 <=q n, m, q <=q 2000$. Подзадача оценивается в 22 баллов 4. Город является деревом $1 <=q n, q <=q 10^5, m = n - 1$. Подзадача оценивается в 24 баллов 5. $1 <=q n, m, q <=q 10^5$. Подзадача оценивается в 30 баллов

Пример:

Вход

9 10 10
1 2
3 2
4 3
2 4
3 5
8 5
9 8
5 6
5 7
7 6
1 2
1 1
1 4
2 5
2 1
1 9
1 7
1 5
2 5
2 2

Ответ

0
2
9
0

Замечание

Граф из первого теста (перед запросом с номером 5)

Можно заметить что выделенная ребро (ребро с индексом 1) соединяет 2 пары вершин: (1, 2) и (1, 4) Но, еще заметим что ребро (2, 4) не соединяет вершины 2 и 4 так как существует путь (2 -> 3 -> 4). ( Hafiz Batyrkhan )

Комментарий/решение

RE 25 test

показать/скрыть код

#include <bits/stdc++.h>

#define ll long long
#define modw 1000000007
#define N 2019
#define fi first
#define se second
#define pb push_back
#define elif else if

using namespace std;

bool used[N][N];
vector<int> a[N];
bool vv[N];
vector< pair<int, int> > pp;

void dfs(int c, int x, pair<int, int> z) // dfs для каждого графа, только без одной вершины
{
	used[c][x] = 1;
	for(int i = 0; i < a[x].size(); i++)
	{
		if(!used[c][a[x][i]])
		{
			if(a[x][i] == z.fi && x == z.se)
			{
				continue;
			}
			if(a[x][i] == z.se && x == z.fi)
			{
				continue;
			}
			//cout << x << endl;
			//cout << a[x][i] << ' ' << x << ' ' << i << "  vv" << endl;
			dfs(c, a[x][i], z);
		}
	}
}

int main()
{
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0; i < m; i++)
	{
		int t1, t2;
		cin >> t1 >> t2;
		t1--;
		t2--;
		a[t1].pb(t2);
		a[t2].pb(t1);
		pp.pb({t1, t2});
	}
	for(int i = 0; i < q; i++)
	{
		int tp, v;
		cin >> tp >> v;
		if(tp == 1)
		{
			if(!vv[v - 1])
				vv[v - 1] = 1;
			else
				vv[v - 1] = 0;
		}
		else
		{
			dfs(i, 0, pp[v - 1]);
			int c1 = 0, c2 = 0;
			for(int j = 0; j < n; j++)
			{
				if(vv[j] && used[i][j] == 0)
				{
					c1++;
					//cout << j + 1 << "   0" << endl;
				}
				elif(vv[j])
				{
					c2++;
					//cout << j + 1 << "   1" << endl;
				}
			}
			cout << c1 * c2 << endl;
		}
	}
    return 0;
}

показать/скрыть код

#include <bits/stdc++.h>
 
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end() 
#define ld long double
 
using namespace std; 
 
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
} 
void win()
{	
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
}
 
int block = 400;
const ld eps = 1e-6; 
 
const int N = 1e6 + 500;
const int mod = 1e9 + 7;
 
const ll hh = 100010683;
const ll hh2 = 150005819;

int n, m, q, timer;
vector<pair<int, int>> g[N];vector<int> g2[N];
int dp[N], tin[N], tout[N], color[N], f[N], u[N], v[N];
bool was[N], good[N];
void dfs(int v)
{
	was[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].f;
		if (was[to] == 0)
			dfs(to), g2[v].pb(to), g2[to].pb(v);
	}	
}
void find_bridges(int v, int p)
{
	was[v] = 1;
	dp[v] = tin[v] = ++timer;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].f, pos = g[v][i].s;
		if (to == p)
			continue;
		if (was[to])
		{
			dp[v] = min(dp[v], tin[to]);
		}
		else
		{
			find_bridges(to, v);
			dp[v] = min(dp[v], dp[to]);
			if (dp[to] > tin[v])
			{
				good[pos] = 1;		
			}
		}
	}
	tout[v] = timer;
}
void dfs2(int v, int p)
{
//	cout << v << '\n';
	tin[v] = ++timer;
	for (int i = 0; i < g2[v].size(); i++)
	{
		int to = g2[v][i];
		if (to != p)
		{
			dfs2(to, v);		
		}
	}
	tout[v] = ++timer;
}
void upd(int pos, int val)
{
	for (int i = pos; i <= N - 200; i |= (i + 1))
	{
		f[i] += val;
	}
}
int get(int pos)
{
	int res = 0;
	for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
	{
		res += f[i];
	}
	return res;
}
int main()
{
	data();              
	win();
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++)
	{
		cin >> u[i] >> v[i];
		g[u[i]].pb({v[i], i});
		g[v[i]].pb({u[i], i});
	}
	find_bridges(1, 0);
	memset(was, 0, sizeof(was));
	timer = 0;
	dfs(1);
	memset(was, 0, sizeof(was));
	dfs2(1, 0);
//	return 0;
	for (int i = 1; i <= q; i++)
	{
		int type, pos;
		cin >> type >> pos;
		if (type == 1)
		{
			if (color[pos] == 0)
			{
				upd(tin[pos], 1);
				color[pos] = 1;
			}
			else
			{
				upd(tin[pos], -1);
				color[pos] = 0;
			}
		}
		else
		{
			if (good[pos] == 0)
			{
				cout << 0 << '\n';
			}	
			else
			{
				int a = u[pos], b = v[pos];
				if (tin[a] < tin[b])
					swap(a, b);
				cout << (get(tout[1]) - (get(tout[a]) - get(tin[a] - 1))) * (get(tout[a]) - get(tin[a] - 1)) << '\n';
			}
		}
	}
}

AC

Accepted

показать/скрыть код

#include<bits/stdc++.h>

#define all(v) v.begin(),v.end()
#define sz(a) a.size()
#define nl "\n"
#define IOI return 0;
#define pb push_back
#define ppb pop_back()
#define ll long long
#define ull unsigned long long
#define ld long double
#define IOS ios_base :: sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define X first
#define Y second


using namespace std;
const int N = (int)1e5 +7;
const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e18 + 7;
const int inf = (int)1e9 + 7;

pii dx[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool used[N],good[N],type[N];
ll tin[N],tout[N],fup[N],sz[N],p[N],t[4*N],timer;
vector<pii> g[N];
vector<int> g2[N];
pii edge[N];
int get(int v) {
    if(p[v]!=v) p[v]=get(p[v]);
    return p[v];
}
void comb(int a, int b) {
    a = get(a);
    b = get(b);
    if(sz[a]>sz[b]) {
        swap(a,b);
    }
    p[a]=b;
    if(a!=b) {sz[b]+=sz[a];sz[a]=0;}
}

void dfs(int v, int pr = 0) {
    used[v]=1;
    tin[v]=fup[v]=++timer;
    for(auto e : g[v]) {
        int to = e.X, id = e.Y;
        if(to==pr) continue;
        if(used[to]) {
            fup[v] = min(fup[v],tin[to]);
        } else {
            dfs(to,v);
            fup[v] = min(fup[v],fup[to]);
            if(fup[to]<=tin[v]) {
                comb(v,to);
            } else {
                good[id] = 1;
            }
        }
    }
}
void DFS(int v, int pr = 0) {
    used[v]=1;
    tin[v]=++timer;
    for(auto to : g2[v]) {
        if(to==pr) continue;
        if(used[to]==0) {
            DFS(to,v);
        }
    }
    tout[v]=timer;
}

void upd(int v, int tl, int tr, int id, int val) {
    if(tl==tr) {
        t[v] += val;
        return;
    }
    int mid = (tl+tr)>>1;
    if(id<=mid) {
        upd(v*2, tl, mid, id, val);
    } else {
        upd(v*2+1, mid+1, tr, id, val);
    }
    t[v]=t[v*2]+t[v*2+1];
}

ll get(int v, int tl, int tr, int l, int r) {
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return t[v];
    int mid = (tl+tr)>>1;
    ll A = get(v*2, tl, mid, l, r);
    ll B = get(v*2+1, mid+1, tr, l, r);
    return A+B;
}

void solve() {
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1; i<=n; ++i) sz[i]=1,p[i]=i;
    for(int i=1,x,y; i<=m; ++i) {
        cin>>x>>y;
        g[x].pb({y,i});
        g[y].pb({x,i});
        edge[i] = {x,y};
    }
    dfs(1);
    for(int i=1; i<=m; ++i) {
        int x = edge[i].X, y = edge[i].Y;
        x = get(x), y = get(y);
        if(x==y) continue;
        g2[x].pb(y);
        g2[y].pb(x);
    }
    timer = 0;
    fill(used+1, used+1+n, 0);
    DFS(get(1));
    while(q--) {
        int tp,i;
        cin>>tp>>i;
        if(tp==1) {
            int x = get(i);
            if(type[i]==0) {
                type[i]=1;
                upd(1,1,n,tin[x],1);
            } else if(type[i]==1) {
                type[i]=0;
                upd(1,1,n,tin[x],-1);
            }
        } else {
            if(!good[i]) {
                cout<<"0\n";
                continue;
            }
            int a = edge[i].X, b = edge[i].Y;
            a = get(a), b = get(b);
            if(tin[a]>tin[b]) {
                swap(a,b);
            }
            ll ALL = t[1];
            ll x = get(1,1,n,tin[b],tout[b]);
            cout<<1ll * x * 1ll * (ALL-x)<<nl;
        }
    }
}


int main() {
    IOS
    int tt=1;
    //cin>>tt;
    while(tt--) {
        solve();
    }
    IOI
}

показать/скрыть код

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>
using vvi = vt< vt<int> >

const int N = 1e5 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

int n, m, q, fup[N], tin[N], tout[N], timer, bridge[N];
vt<int> used(N), g[N];
vt<pii> adj[N];

void dfs1 (int v, int p = 0) {
	used[v] = 1;
	tin[v] = fup[v] = ++timer;
	for (auto [to, id]: adj[v]) {
		if (to != p) {
			if (used[to]) fup[v] = min(fup[v], tin[to]);
			else {
				dfs1(to, v);
				fup[v] = min(fup[v], fup[to]);
				if (fup[to] > tin[v]) bridge[id] = 1;
			}
		}
	}
}

void make (int v) {
	used[v] = 1;  
	for (auto [to, id]: adj[v]) {
		if (!used[to]) {
        	make(to);
        	g[v].pb(to);
        	g[to].pb(v);
        }
	}
}

void dfs (int v, int p = 0) {
	tin[v] = ++timer;
	for (auto to: g[v]) {
		if (to != p) {
			dfs(to, v);
		}
	}
	tout[v] = timer;
}

int t[4 * N];

void upd (int pos, int val, int v = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		t[v] += val;  
		return;
	}
	int tm = tl + tr >> 1;
	if (pos <= tm) upd(pos, val, v << 1, tl, tm);
	else upd(pos, val, v << 1 | 1, tm + 1, tr);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

int get (int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t[v];
	int tm = tl + tr >> 1;
	int a = get(l, r, v << 1, tl, tm);
	int b = get(l, r, v << 1 | 1, tm + 1, tr);
	return a + b;
}

void solve () {
	cin >> n >> m >> q;
	used.resize(n + 5, 0);
	int x[m + 1], y[m + 1];
	for (int i = 1; i <= m; i++) {
		cin >> x[i] >> y[i];
		adj[x[i]].pb({y[i], i});
		adj[y[i]].pb({x[i], i});
	}
	dfs1(1);
	fill(all(used), 0);
	make(1);
	timer = 0;
	dfs(1);
	vt<int> h(n + 1, 0);
	for (int j = 1; j <= q; j++) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int k;
			cin >> k;
			if (h[k]) upd(tin[k], -1);
			else upd(tin[k], 1);
			h[k] ^= 1;
		}
		if (tp == 2) {
			int i;
			cin >> i;
			if (!bridge[i]) {
				cout << "0\n";
				continue;
			}
			int a = x[i], b = y[i];
			if (tin[b] > tin[a]) swap(a, b);
			int k = (get(1, tout[a]) - get(1, tin[a] - 1));
			cout << (t[1] - k) * k << '\n'; 
		}
	}  
	cout << '\n';
}

bool testcases = 0;
                  
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

показать/скрыть код

// Problem: A. Yosik - город где сбываются мечты
// Contest: Codeforces - IOI contest #5 (div 1 + 2)
// URL: https://codeforces.com/group/2wABagZcmo/contest/505340/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

#define int		    long long
#define all(x) 		x.begin(), x.end()
#define allr(x) 		x.rbegin(), x.rend()
#define sz          size()
#define yes			"YES"
#define no			"NO"
#define ok			"OK\n"
#define IOI			ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pf			push_front
#define pb			push_back
#define S			second
#define F			first

using namespace std;

const int N = 2e5 + 5;
const int NN = 3e6 + 5;
const int mod = 1e9 + 7;
const int inf = 1e11;

int n, m, q;

vector<pair<int, int>> g[N];

vector<int> gr[N];

vector<pair<int, int>> v;

int was[N];

int vip[N];

int tp[4 * N], tin[N], fup[N], tout[N], timer;

int brd[N], color[N];


void upd(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tp[v] += val;
		return;
	}
	int mid = tl + tr >> 1;
	if (pos <= mid) upd(v + v, tl, mid, pos, val);
	else upd(v + v + 1, mid + 1, tr, pos, val);
	
	tp[v] = tp[v + v] + tp[v + v + 1];
}

int get(int v, int tl, int tr, int l, int r) {
	if (tr < l or r < tl) {
		return 0;
	}
	if (l <= tl and tr <= r) {
		return tp[v];
	}
	int mid = tl + tr >> 1;
	int res1 = get(v + v + 1, mid + 1, tr, l, r);
	int res2 = get(v + v, tl, mid, l, r);
	return res1 + res2;
}

void DFS(int v, int col) {
	color[v] = col;
	for (auto& p : g[v]) {
		int x = p.S;
		int to = p.F;
		if (brd[x] == 1) {
			continue;
		}
		if (color[to] == 0) DFS(to, col);	
	}
}

void dfs(int v, int pr) {
	was[v] = 1;
	tin[v] = fup[v] = ++timer;	
	for(auto& p : g[v]) {
		int to = p.F;
		int x = p.S;
		if (to == pr) continue;
		if (was[to] == 1) {
			fup[v] = min(fup[v], fup[to]);
		}
		else {
			dfs(to, v);
			fup[v] = min(fup[v], fup[to]);
			if (fup[to] > tin[v]) {
				//cout << to <<  " " << v << endl;
				brd[x] = 1;
			}
		}
	}
}

void ddfs(int v, int pr) {
	tin[v] = ++timer;
	for (auto& to : gr[v]) {
		if (to != pr) {
			ddfs(to, v);
		}
	}
	tout[v] = timer;
}

void legenda_ne_umret() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb({y, i});
		g[y].pb({x, i});
		v.pb({x, y});
	}	
	
	dfs(1, 1);
	int col = 1;
	for (int i = 1; i <= n; i++) {
		if (color[i] == 0) {
			DFS(i, col);
			col++;
		}
	}
	for (auto& p : v) {
		int x = p.F;
		int y = p.S;
		if (color[x] != color[y]) {
			gr[color[x]].pb(color[y]);
			gr[color[y]].pb(color[x]);
		}
	}
	timer = 0;
	ddfs(1, 1);
	for (int i = 1; i <= q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int x;
			cin >> x;
			if (vip[x]) {
				upd(1, 1, n, tin[color[x]], -1);
			}
			else upd(1, 1, n, tin[color[x]], 1);
			vip[x] = (vip[x] ^ 1);
		}
		else {
			int x;
			cin >> x;
			if (brd[x] == 0) {
				cout << 0 << '\n';
				continue;
			}
			int fr = color[v[x - 1].F];
			int sc = color[v[x - 1].S];
			if (tin[fr] <= tin[sc] and tout[sc] <= tout[fr]) swap(fr, sc);
			int k = get(1, 1, n, tin[fr], tout[fr]);
			cout << (tp[1] - k) * k<< '\n';
		}
	}
}

signed main() {
    IOI;
    //freopen("haybales.in", "r", stdin);
    //freopen("haybales.out", "w", stdout);
///////////////////////////////////////////
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "Case " << i << ":\n";
        legenda_ne_umret();
        cout << '\n';
    }
}