oj.uz

Submission #757337

# Submission time Handle Problem Language Result Execution time Memory
757337 2023-06-13T05:32:09 Z shadow_sami Inside information (BOI21_servers) C++17
5 / 100
 201 ms 32516 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 4000+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
ll tnc[mx];
vi lis[mx];
bool vis[mx][mx];
vi vv;
unordered_map<ll,ll> umap;

void unite(ll u,ll v){
	bool mark[mx];
	memset(mark,false,sizeof(mark));
	fip(1,n+1)
		if(vis[u][i]){
			tnc[i]--;
			mark[i] = 1;
		}
	fip(1,n+1)
		if(vis[v][i]){
			tnc[i]--;
			mark[i] = 1;
		}
	fip(1,n+1)
		if(mark[i]){
			vis[u][i] = vis[v][i] = 1;
			tnc[i] += 2;
		}
	return;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m;
        fip(1,n+1){
        	tnc[i]++;
        	vis[i][i] = 1;
        }
        int sr,de;
        char c;
        fip(0,n+m-1){
        	cin>>c;        	
        	if(c=='S'){
        		cin>>sr>>de;
        		debug(sr);
        		debug(de);
        		unite(sr,de);
        	}
        	else if(c=='Q'){        		
        		cin>>sr>>de;
        		f = 0;
        		f = vis[sr][de];
        		cout<< (f ? "yes" : "no")<<nli;
        	}else{
        		cin>>de;
        		cout<<tnc[de]<<nli;
        	}
        }
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1108 KB Output is correct
2 Correct 154 ms 17920 KB Output is correct
3 Correct 168 ms 17928 KB Output is correct
4 Correct 150 ms 17916 KB Output is correct
5 Correct 138 ms 17904 KB Output is correct
6 Correct 201 ms 18068 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1108 KB Output is correct
2 Correct 154 ms 17920 KB Output is correct
3 Correct 168 ms 17928 KB Output is correct
4 Correct 150 ms 17916 KB Output is correct
5 Correct 138 ms 17904 KB Output is correct
6 Correct 201 ms 18068 KB Output is correct
7 Correct 25 ms 1728 KB Output is correct
8 Correct 129 ms 17520 KB Output is correct
9 Correct 142 ms 17652 KB Output is correct
10 Correct 127 ms 17584 KB Output is correct
11 Correct 140 ms 17484 KB Output is correct
12 Correct 183 ms 17804 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1108 KB Output is correct
2 Runtime error 20 ms 32504 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1108 KB Output is correct
2 Runtime error 20 ms 32504 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 992 KB Output is correct
2 Runtime error 20 ms 32468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 992 KB Output is correct
2 Runtime error 20 ms 32468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1036 KB Output is correct
2 Runtime error 23 ms 32504 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1036 KB Output is correct
2 Runtime error 23 ms 32504 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1004 KB Output is correct
2 Runtime error 20 ms 32480 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1004 KB Output is correct
2 Runtime error 20 ms 32480 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1112 KB Output is correct
2 Correct 140 ms 17960 KB Output is correct
3 Correct 185 ms 17860 KB Output is correct
4 Correct 182 ms 17816 KB Output is correct
5 Correct 154 ms 17916 KB Output is correct
6 Correct 176 ms 17856 KB Output is correct
7 Correct 24 ms 1812 KB Output is correct
8 Runtime error 19 ms 32516 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1112 KB Output is correct
2 Correct 140 ms 17960 KB Output is correct
3 Correct 185 ms 17860 KB Output is correct
4 Correct 182 ms 17816 KB Output is correct
5 Correct 154 ms 17916 KB Output is correct
6 Correct 176 ms 17856 KB Output is correct
7 Correct 24 ms 1812 KB Output is correct
8 Runtime error 19 ms 32516 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -