10-11 класс

Есеп F. Yosik - армандар орындалатын қала

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

1 second

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

256 megabytes

Yosik - миллиондаған армандар орындалатын Қазақстанның қаласы. Сонымен бірге, Yosik - бүкіл әлемнің ең маңызды экономикалық орталығы. Yosik, Лондон және Токио сияқты, әлемдік экономиканың үш негізгі орталығының бірі деп аталады. Ал, әрине, CMaster мэрі болмаса, қала мұндай танымалдылыққа ие болмас еді. Ол осы мақсатқа жету үшін бар күш-жігерін салған. Бірақ басқа елдер арасындағы экономикалық текетірес Yosik экономикасына теріс әсер етті. Мэр қалада кейбір жолдардың сапасын жақсартқысы келеді. Ал қалада $n$ аудан бар. Әр ауданның экономикалық жағдайы екі түрлі сөзбен сиппаталады: Жоғары немесе Төмен. Мэр CMaster қаланың жолдарды дағдарыс кезінде жақсарту туралы дұрыс шешім қабылдауы үшін, ол осы жол қанша жағдайы Жоғары екі ауданның арасында орналасқанын білуі қажет. Яғни екі ауданның арасындағы бағыттардың бәрі осы жолдан өтсе ғана, жол өте Жоғары маңыздылықтары бар $(a, b)$ аудандарын біріктіреді. Және $q$ түрлі оқиғалар бар: 1) $v$ $(1 <=q v <=q n)$ ауданының статусын өзгерту, Төмен болса, Жоғары, әйтпесе оны Төменге өзгертіңіз. 2) $i$-ші $(1 <=q i <=q m)$ жол үшін, осы жол біріктіретін Жоғарғы маңыздылығы бар $(a, b)$ екі қаланың санын айтыңыз, яғни осы жол Жоғары мәртебесі бар $(a, b)$ арасындағы барлық бағыттарда орналасқан аудандарының санын айтыңыз. Ал жұптар $(a, b)$ және $(b, a)$ бірдей деп есептеледі. Қаланы $n$ шыңдары және $m$ жолдары бар байланыстырылған бағытталмаған граф ретінде көрсетуге болады. Әрбір ауданның Жоғары немесе Төмен экономикалық маңызы бар. Бастапқыда барлық аудандардың экономикалық маңызы Төмен. Ауданды өзімен байланыстыратын жол болуы мүмкін (ілмек), бірақ бірнеше бірдей жолдар жоқ, яғни бірдей екі шыңды жалғайтын жолдар жоқ.

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

Бірінші жолда $n$, $m$ және $q$, облыстардың саны, жолдар мен оқиғалар саны берілген. Содан кейін $m$ сан берілген - Yosik-тегі бағытталмаған жолдар. Графта екі бірдей жолдар жоқ, бірақ ілмектер болуы мүмкін. Содан кейін сізге $q$ сұранымдар $(type, number)$ беріледі. Егер $type = 1$ болса, онда бұл сұрақтың бірінші түрі және number, $(1 <=q number <=q n)$ шыңның санын көрсетеді. Егер $type = 2$ болса, онда бұл сұраулардың екінші түрі және $number$, $(1 <=q number <=q m)$ - кірістің деректерінің реті бойынша жол санын білдіреді.

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

2-нші түрдің әрбір сұрауы үшін, сіз осы жол қанша маңыздылығы Жоғары шыңдардың $(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 ұпаймен бағаланады

Пример:

\exmpfile{example.01}{example.01.a}%

Замечание

Бірінші мысалдағы қала нұсқасы (5-нші оқиғаға дейін) \begin{center} \includegraphics[width=10cm,height=7cm]{image.eps} \end{center} 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';
    }
}