Submission #966699

#TimeUsernameProblemLanguageResultExecution timeMemory
966699AmrToy Train (IOI17_train)C++17
0 / 100
164 ms10600 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define sz size() #define F first #define S second #define all(x) (x).begin(),(x).end() const int N = 1e5+2; ll tim = 1; ll vis[N]; vector<pair<ll,ll> > out; vector<ll> vv; vector<ll> adj[N], adj2[N], scc[N]; vector<ll> nodes; ll ok = 0; vector<int> ans; ll p[N]; void dfs(ll x) { if(vis[x]) return ; vis[x] = 1; for(int i = 0; i < adj[x].sz; i++) { ll y = adj[x][i]; dfs(y); } out.push_back({tim++,x}); } void dfs2(ll x) { if(vis[x]) return; vis[x] = 1; vv.push_back(x); for(int i = 0; i < adj2[x].sz; i++) { ll y = adj2[x][i]; dfs2(y); } } void dfs3(ll x) { if(vis[x]) return; ok|=ans[x]; vis[x] = 1; for(int i =0; i < scc[x].sz; i++) { ll y = scc[x][i]; dfs3(y); } } std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { ll n = a.sz; ll m = u.sz; ans.resize(n); for(int i = 0; i < m ;i++) { ll x, y; x=u[i],y=v[i]; adj[x].push_back(y); adj2[y].push_back(x); } for(int i = 0; i < n; i++){ if(!vis[i]) dfs(i); } sort(all(out)); reverse(all(out)); for(int i = 0; i < n; i++) vis[i] = 0; for(int i = 0; i < n; i++) { ll x = out[i].S; if(vis[x]) continue; vv.clear(); dfs2(x); for(int j = 0; j < vv.sz; j++) p[vv[j]] = x,ans[x] = max(ans[x],r[vv[j]]); nodes.push_back(x); } for(int i = 0; i < n ;i++) vis[i] = 0; for(int i = 0; i < n ;i++) { // cout << p[i] << " "; for(int j = 0; j < adj[i].sz; j++) { ll x = i, y = adj[i][j]; if(p[x]!=p[y]) scc[p[x]].push_back(p[y]); } } for(int i = 0; i < nodes.sz ;i++) { ok = 0; for(int j = 0; j < n; j++) vis[j] = 0; dfs3(nodes[i]); ans[nodes[i]]|=ok; } for(int i = 0; i < n; i++) ans[i] = ans[p[i]]; return ans; }

Compilation message (stderr)

train.cpp: In function 'void dfs(ll)':
train.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < adj[x].sz; i++)
      |                      ^
train.cpp: In function 'void dfs2(ll)':
train.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < adj2[x].sz; i++)
      |                      ^
train.cpp: In function 'void dfs3(ll)':
train.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i =0; i < scc[x].sz; i++)
      |                     ^
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j = 0; j < vv.sz; j++) p[vv[j]] = x,ans[x] = max(ans[x],r[vv[j]]);
      |                          ^
train.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j = 0; j < adj[i].sz; j++)
      |                          ^
train.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < nodes.sz ;i++)
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...